c++ - Detecting cycle in an undirected graph using iterative DFS? -

so, implemented dfs in iterative manner following method:

void dfsiter (graph * mygraph, int foo, bool arr[]) {     stack <int> mystack;     mystack.push(foo);     while (mystack.empty() == false)     {         int k = mystack.top();         mystack.pop();         if (arr[k] == false)         {             cout<<k<<"\t";             arr[k] = true;             auto = mygraph->edges[k].begin();             while (it != mygraph->edges[k].end())             {                 if (arr[*it] == false)                 {                     mystack.push(*it);                 }                 it++;             }          }     } } 

the above code works fine. now, want detect cycles in undirected graph using above code (iterative dfs). now, read that, if unexplored edge leads node visited before, graph contains cycle. therefore, want ask you, how keep track of this?

i have taken graph this:

class graph {     public:     int vertices;     vector < vector<int> > edges; }; 

should change above to:

class graph {     public:     int vertices;     vector < vector<pair<int,bool> > edges; }; 

where bool each edge marked true? , changes need in above code dfs detecting cycle? tried couldn't think of way of doing it. thanks!

you can store "father" node f in dfs tree each vertex v, i.e. vertex dfs came vertex v. can stored in stack example. in case store pairs in stack, first value vertex v , second 1 father f.

an undirected graph has cycle if , if meet edge vw going visited vertex w, not father of v.

you can see modified , cleaned code below.

bool hascycle (graph * mygraph, int start, bool visited[]) {     stack <pair<int, int> > mystack;     mystack.push(make_pair(start, -1));     visited[start] = true;      while (!mystack.empty())     {         int v = mystack.top().first;         int f = mystack.top().second;         mystack.pop();          const auto &edges = mygraph->edges[v];         (auto = edges.begin(); != edges.end(); it++)         {             int w = *it;             if (!visited[w])             {                 mystack.push(make_pair(w, v));                 visited[w] = true;             }             else if (w != f)                 return true;         }     }     return false; } 

note: if graph disconnected, must start dfs several vertices, ensuring whole graph visited. can done in o(v + e) total time.