We can use DFS to find a cycle in a given graph. The idea is that a cycle exists if we can find back edge in the graph. First I just want to detect if a cycle exists, if so return true else false. Here is what I have got so far:DFS(G,s)  for all v in V do    color[v] <- white; parent[v] <- nil  end for  DFS-Visit(s)G is the given graph and s is the starting node.DFS-Visit(u)  color[u] <- gray  for all v in Ajd[u] do    if color[v] = gray then       return true // found cycle    if color[v] = white AND DFS-Visit(v) then       return true // found cycle rooted in v  end for  color[u] <- black  return false // no cycle foundAjd[u] is the list of u's neighbours. So by processing the children of u we might discover a node that is marked gray. If so u and v are connected with a back edge and we found a cycle.Now I want to extend this algorithm to output the found cycle. Any ideas on how to do that? I thought about using a stack and simply push all u's in DFS-Visit onto the stack. When true is returned I can output the cycle by taking the nodes from the stack. What do you think?Using a stack won't solve my problem, because the stack will contain nodes that are not part of the cycle.I have another idea. When we found a cycle we know v=u. To print the cycle we have to go back using the parent list until we reach u:DFS-Visit(u)  color[u] <- gray  foundCycle <- false  vv <- nil  for all v in Ajd[u] do    if color[v] = gray then       vv <- v       foundCycle <- true // found cycle       break    if color[v] = white then       parent[v] <- u       DFS-Visit(v)  end for  color[u] <- black  if foundCylce then      printCycle(vv, u)printCycle(v,u)  if v=u then     print v  else     print v     printCycle(parent[v], u)
Output cycle found by DFS
algorithms;graphs;graph traversal;searching
When true is returned I can output the cycle by taking the nodes from the stack.The stack contains the nodes you still have to visit, so they can not be part of the cycle.There are at least two options to actually obtain data from a DFS.Create the DFS tree explicitly; this gives you full information.If you only want one cycle, you can store a pointer to the visited node's parent (the tree edge) instead of labelling it gray.