3
$\begingroup$

I have been trying to implement an algorithm to detect cycles (probably how many of them) in a directed and undirected graph. That is the code should apply for both directed and undirected graphs.

Using DFS or topological sort is mostly recommended in various posts. But largely, everything is addressed for undirected graph.

This link describes one approach for cycle detection. To my understanding this works for directed graphs.

This link has the code for cycle detection in undirected graphs. but I fail to understand how it ignores the back edge. That is it must ignore any cycles with two nodes, say D to C and C to D. which means it must remember it parent as the DFS recurses. But the code does not seem take care of that.

Any suggestions welcome..

enter image description here

$\endgroup$
1
$\begingroup$

Take a look at the answers for finding all cycles in graph.

You can transform undirected graph into a directed graph quite easily: for every edge (u,v) in your original graph G, put two edges (u --> v) and (v --> u) into your new directed graph T. Apply any of the algorithms that find cycles in a directed graph on T. However, notice that any undirected edge transforms into a directed cycle (u - v - u), so if your original graph was initially undirected, you can ignore cycles of length 2 at the end.

$\endgroup$

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.