CODEWITHSUNDEEP
c++
user3747190
user3747190

Reputation: 1707

Define "visited" variable for a node in a graph

I have written the code for graph that you can see on following link.

Calculating outdegree of a node in Graph

Now, I need to write BFS and DFS for the same. For that I need to have a variable "visited" to define whether the node is visited or not. I realised that I will have to include this variable in the 

class Graph{

vector<pair<pair<**bool**,T>, list<T2> > > node;

}

Here bool is the condition whether the node is visited or not. For this I had to do the changes in the entire code. Is there any other way, where I can include the variable without doing much modification in the code ?

Ok, I got it. Its quite simple. Sorry to ask such a question. I can define another 

vector<bool> visited

in the BFS function. I will update the code after writing the function. Once again sorry.

Upvotes: 0

Views: 162

Answers (1)

Dewfy
Dewfy

Reputation: 23634

Placing marker of visiting inside class is not good idea - because you can do it only once - after that you have to reset everything before starting algorithm second time. As an alternative you have 2 options:

  • Instead of bool use some number - that unique identifies number of algorithm was applied, so before test if node of visited you have to increase global apply counter and check if version of node strictly less than global apply counter.

  • You can declare hash-map (for c++11 use unordered_map ) that tracks IDs of node (as a not good, but workable example use pointer to node). So if id of node is exists inside hash-map than node was visited. After algorithm was applied just destroy the map

I'd prefer second case.

p.s. And yes, comment of @a_guest - is correct - create your class Node

Upvotes: 2

Related Questions