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)
