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 found Ajd[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) 
