java - 在无向图中查找所有循环

Question

我正在使用 Algorithms 4th edition稍微完善一下我的图论。书中附有大量图形处理代码。
目前，我遇到了以下问题: 如何在无向图中找到所有循环？我正在寻找修改 existing code for cycle detection这样做。

这里是重要的部分:

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 只会找到两个后缘。

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