Find all cycles in undirected graph

Question

I am using Algorithms 4th edition to polish up my graph theory a bit. The books comes with a lot of code for graph processing.
Currently, I am stuck with the following problems: How to find all cycles in an undirected graph? I was looking to modify the existing code for cycle detection to do that.

Here is the important part:

private void dfs(Graph G, int u, int v) {
        marked[v] = true;
        for (int w : G.adj(v)) {

            // short circuit if cycle already found
            if (cycle != null) return;

            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(G, v, w);
            }

            // check for cycle (but disregard reverse of edge leading to v)
            else if (w != u) {
                cycle = new Stack<Integer>();
                for (int x = v; x != w; x = edgeTo[x]) {
                    cycle.push(x);
                }
                cycle.push(w);
                cycle.push(v);
            }
        }
    }

Now, if I were to find ALL cycles, I should remove the line that returns when a cycle is found and each time a cycle is created I would store it. The part I cannot figure out is: when does the algorithm stop? How can I be sure I have found all cycles?

Can the above code even be modified in a way to allow me to find all cycles?

Answer 1

Cycle detection is much easier than finding all cycles. Cycle detection can be done in linear time using a DFS like you've linked, but the number of cycles in a graph can be exponential, ruling out an polytime algorithm altogether. If you don't see how this could be possible, consider this graph:

1 -- 2
|  / |
| /  |
3 -- 4

There are three distinct cycles, but a DFS would find only two back-edges.

As such, modifying your algorithm to find all cycles will take a fair bit more work than simply changing a line or two. Instead, you have to find a set of base cycles, then combine them to form the set of all cycles. You can find an implementation of an algorithm that'll does this in this question.