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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\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, 2013 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, 2013 at 13:00
  • $\begingroup$ Suppose you've got a figure-eight. Would that be three cycles, or just two? $\endgroup$
    – Nobbynob Littlun
    Aug 15, 2013 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, 2017 at 15:07
  • 1
    $\begingroup$ If possible please add the images from the broken links directly to the answer of the question $\endgroup$
    – StayOnTarget
    Jan 12, 2018 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!

Improve this answer
$\endgroup$
3
  • $\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, 2013 at 21:07
  • $\begingroup$ if it is undirected, backedges still makes sense ? $\endgroup$
    – berkay
    Sep 23, 2015 at 18:34
  • $\begingroup$ @berkay DFS makes perfect sense for undirected graphs. $\endgroup$
    – Yuval Filmus
    Sep 23, 2015 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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