single algorithm to work on both directed and undirected graph to detect cycles?

Question

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..

Answer 1

For a Directed Graph - we keep track of the recursion stack. For an edge (u,v), if we currently are processing u, and we see that v is in the recursion stack, then we have a Cycle.

For Undirected Graph - we look construct a parent array while we are traversing with DFS. Similar situation, for an edge (u,v) while processing u, if we see that v is Visited && not the parent of u, then we have a cycle.

I hope this helps!

Answer 2

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.