Output cycle found by DFS

Question

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)

Answer 1

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.