1
$\begingroup$

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)
$\endgroup$
  • $\begingroup$ What do you think? Does your method work? $\endgroup$ – Yuval Filmus Sep 7 '16 at 21:57
  • $\begingroup$ @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. $\endgroup$ – Lost in OWL Sep 7 '16 at 22:07
  • 1
    $\begingroup$ Great, so you should spend some more time thinking on this. $\endgroup$ – Yuval Filmus Sep 7 '16 at 22:27
  • $\begingroup$ @YuvalFilmus check out my updated question $\endgroup$ – Lost in OWL Sep 8 '16 at 11:07
  • 1
    $\begingroup$ If you have a candidate solution, try to prove that it works. $\endgroup$ – Yuval Filmus Sep 8 '16 at 14:09
2
$\begingroup$

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.
$\endgroup$
  • 1
    $\begingroup$ Thanks. Can you eleborate the two options? $\endgroup$ – Lost in OWL Sep 8 '16 at 7:11
  • 2
    $\begingroup$ I could, but I won't. Consider fleshing things out a useful exercise. :) $\endgroup$ – Raphael Sep 8 '16 at 7:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.