C++ question, I\'m not sure how to use an unordered map to write this function.

Question

C++ question, I'm not sure how to use an unordered map to write this function.

CycleFinder: traverse the graph and determine the node(s) that start cycle(s) in the graph. Use the unordered map data structure in the STL to keep track of the nodes that have been visited. Assumptions: Unique keys, Simple graphs with cycles (no weirdness), e.g., use the graph: 0 rightarrow 1 rightarrow 2 rightarrow 3 rightarrow 0 No need to worry about cases like 4 rightarrow 0 rightarrow 1 rightarrow 2 rightarrow 3 rightarrow 0 (unless you want to!)

Explanation / Answer

We just need the unordered map to check the node whether it has been visited or not. You could take any of the program and modify it for the unordered map usage. If you know how to find a cycle, this will be probably easy for you. Just initialize an unordered map with int to keep track of vertex and bool to check whether the vertex has been visited or not. Here you can check from my code:

bool cycleFinder() //checks whether a graph is cyclic or not
{
unordered_map<int, bool> umap; //initialize the unordered map
bool *recStack = new bool[V];
for(int i = 0; i < V; i++)
{
umap[i]=false; //mark all the vertices to be not visited
recStack[i] = false;
}
for(int i = 0; i < V; i++) //for each of the vertex
if (recGraph(i, &umap, recStack)){ //check whether it forms a unordered map
return true; //if true, return true
}

return false; //else no cycle
}

bool recGraph(int v, unordered_map<int, bool> *umap, bool *recStack) //takes the vertex, unordered map and an array
{
bool check = umap->at(v); //checks if the vertex has been visited or not
if(!check) //if not
{
umap->at(v) = true; //mark the current vertex as visited
recStack[v] = true; //current vertex on the recursion stack
list<int>::iterator i; //iterate for all the vertices adjacent to this
for(i = adj[v].begin(); i != adj[v].end(); ++i)
{
check = umap->at(*i);
if ( !check && isCyclicUtil(*i, umap, recStack) ) //check conditions
return true; //if cyclic
else if (recStack[*i])
return true; //if cyclic
}

}
recStack[v] = false; //removing the vertex from the recursion stack
return false; // if not
}

You can also add   cout << "Vertex: " << i << " "; in the cycleFinder function to print the vertex from which the cycle is startting. If you have further doubt let me know in the comments.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.