5
$\begingroup$

I want to detect cycles in an undirected graph such that I get a list of all edges/vertices which form each cycle. For a graph G({a,b,c,d}, {a-b, b-c, c-d, d-a, b-d}) this would be {a, b, c, d}, {a, b, d}, {b, c, d}.

I have read this and I think that when the iterative pseudocode from Wikipedia finds a back-edge then I can say the graph has a cycle. But I don't know how to find out which vertices/edges the cycle consists of.

Can you please help with an algorithm which would take a graph as input (or the information from DFS) and output list of lists describing the cycles?

$\endgroup$
7
$\begingroup$

You're almost there, but when you find a back edge you already have all the information you need to describe the cycle it forms. Also, there's a bit of a complication where you might find duplicate cycles. Or you might not. Do you consider {A, B, C} to be the same cycle as {C, B, A}? What about {B, C, A}? Depends on what you're doing, but let's assume they're equivalent.

So you've got a graph you're DFSing. illustration http://imageshack.us/a/img687/1598/tjd.gif.

And you go down one branch and detect a few cycles. Cool. illustration http://imageshack.us/a/img14/9295/4bo.gif

But you haven't explored all possibilities, so you unwind the stack and take the next branch. You find some more cycles. Groovy. illustration http://imageshack.us/a/img818/3851/t69.gif

The adventure continues. You go down another path and find another cycle. Good. illustration http://imageshack.us/a/img543/48/c5mb.gif

No, wait. BAD. You've got two equivalent cycles. And when you unwind to having only explored A-B, and take A-B-E this time, that's going to reveal more duplicates. You'd need a way to get rid of those, if they are a problem in your application.

$\endgroup$
  • $\begingroup$ I forgot to use predecessors list! :-) This reminded me and helped me to figure out how to use them - it seems that my app finds the cycles correctly. For anyone looking for a way how to get rid of duplicates simply order the cycle (in this example lexicographically) and compare each element. $\endgroup$ – A123321 Aug 10 '13 at 11:20
  • $\begingroup$ Correction: Going trough predecessors list is not enough, another DFS needs to be done to find all cycles which the back edge can create (/be part of). $\endgroup$ – A123321 Aug 10 '13 at 13:00
  • $\begingroup$ Suppose you've got a figure-eight. Would that be three cycles, or just two? $\endgroup$ – AndrewK Aug 15 '13 at 0:25
  • $\begingroup$ Seems to be a nice answer, but... external image hosting doesn't live forever, and, as expected, they're gone! Could you repost them inside the question ? $\endgroup$ – kebs Oct 23 '17 at 15:07
  • $\begingroup$ If possible please add the images from the broken links directly to the answer of the question $\endgroup$ – DaveInCaz Jan 12 '18 at 17:10
4
$\begingroup$

Make sure that you understand what DFS is doing and why a back-edge means that a graph has a cycle (for example, what does this edge itself has to do with the cycle). If you truly understand why the connection between back-edges and cycles, it should not be difficult to understand how the cycle can be found from the DFS, and then to write out an algorithm employing this knowledge. Good luck!

$\endgroup$
  • $\begingroup$ I see the result of DFS without back-edges as a tree and these back-edges create the cycles. I think I should follow the path from the back edges but I fail to understand how to get back to the edge I started from as the possibilities to go there create another tree. $\endgroup$ – A123321 Aug 9 '13 at 21:07
  • $\begingroup$ if it is undirected, backedges still makes sense ? $\endgroup$ – berkay Sep 23 '15 at 18:34
  • $\begingroup$ @berkay DFS makes perfect sense for undirected graphs. $\endgroup$ – Yuval Filmus Sep 23 '15 at 22:36

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.