Output cycle found by DFS

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)
• What do you think? Does your method work? – Yuval Filmus Sep 7 '16 at 21:57
• @YuvalFilmus I just realize that the stack most likely will contain nodes that are not part of the cycle. So no, I think my method won't work. Instead of returning true/false I could return the actual node. But it is not clear to my how that should work. – Lost in OWL Sep 7 '16 at 22:07
• Great, so you should spend some more time thinking on this. – Yuval Filmus Sep 7 '16 at 22:27
• @YuvalFilmus check out my updated question – Lost in OWL Sep 8 '16 at 11:07
• If you have a candidate solution, try to prove that it works. – Yuval Filmus Sep 8 '16 at 14:09