查找无向图中的所有循环

Question

我正在使用算法第4版来稍微改进我的图论.这些书附带了大量的图形处理代码.
目前,我遇到了以下问题:如何在无向图中找到所有周期？我想修改现有的循环检测代码来做到这一点.

这是重要的部分:

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);
            }
        }
    }

现在,如果我要找到所有循环,我应该删除在找到循环时返回的行,并且每次创建一个循环时我都会存储它.我无法弄清楚的部分是:算法什么时候停止？我怎么能确定我找到了所有周期？

以上代码甚至可以通过某种方式修改,以便我找到所有循环？

Answer 1

循环检测比查找所有循环容易得多。循环检测可以使用您链接的 DFS 在线性时间内完成，但图中的循环数可以是指数级的，从而完全排除了多时间算法。如果您不明白这是怎么可能的，请考虑此图：

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

存在三个不同的循环，但 DFS 只能找到两个后沿。

因此，修改算法来查找所有周期将比简单地更改一两行需要更多的工作。相反，您必须找到一组基本循环，然后将它们组合起来形成所有循环的集合。您可以在这个问题中找到执行此操作的算法的实现。