c++ - Checking for a cycle in an undirected graph using DFS? -

so, made following code dfs:

void dfs (graph * mygraph, int foo, bool arr[]) // here, foo source vertex {     if (arr[foo] == true)         return;     else     {         cout<<foo<<"\t";         arr[foo] = true;         auto = mygraph->edges[foo].begin();         while (it != mygraph->edges[foo].end())         {             int k = *it;             if (arr[k] == false)             {                 //cout<<k<<"\n";                 dfs(mygraph,k,arr);                 //cout<<k<<"\t";             }             it++;         }     }     //cout<<"\n"; } 

now, read in undirected graph, if while dfs, returns same vertex again, there cycle. therefore, did this,

bool checkcycle( graph * mygraph, int foo, bool arr[] ) {      bool result = false;     if (arr[foo] == true)     {         result = true;     }     else     {         arr[foo] = true;         auto = mygraph->edges[foo].begin();         while (it != mygraph->edges[foo].end())         {             int k = *it;             result = checkcycle(mygraph,k,arr);                  it++;         }     }     return result; }    

but, checkcycle function returns true if no cycle. why that? there wrong function? there no execution problem, otherwise have debugged, seems wrong in logic.

notice function doesn't quite think does. let me try step through what's happening here. assume following relationships: (1,2), (1,3), (2,3). i'm not assuming reflexibility (that is, (1,2) not imply (2,1)). relationships directed.

1. start node 1. flag visited
2. iterate children (2 , 3)
3. when in node 2, recursively call check cycle. @ point 2 flagged visited.
4. the recursive call visits 3 (depth search). 3 flagged visited
5. call step 4 dies returning false
6. call step 3 dies returning false
7. we're @ step 2. we'll iterate node 3, has been flagged in step 4. returns true.

you need stack of visited nodes or search original node. stack detect sub-cycles (cycles not include original node), takes more memory.

edit: stack of nodes not bunch of true/false values, instead stack of node numbers. node has been visited in current stack trace if it's present in stack.

however, there's more memory-friendly way: set arr[foo] = false; calls die. this:

bool checkcycle( graph * mygraph, int foo, bool arr[], int previousfoo=-1 ) {     bool result = false;     if (arr[foo] == true)     {         result = true;     }     else     {         arr[foo] = true;         auto = mygraph->edges[foo].begin();         while (it != mygraph->edges[foo].end())         {             int k = *it;              // should prevent going previous node             if (k != previousfoo) {                 result = checkcycle(mygraph,k,arr, foo);             }              it++;         }          // add         arr[foo] = false;     }     return result; }    

i think should enough.

edit: should support undirected graphs. node: code not tested

edit: more elaborate solutions see strongly connected components

edit: answer market accepted although concrete solution given in comments. read comments details.