HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Detecting cycles in undirected graph

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
undirecteddetectingcyclesgraph

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#13693, answer score: 7

Revisions (0)

No revisions yet.