algorithm - 在有向图和无向图上工作以检测循环的单一算法？

Question

我一直在尝试实现一种算法来检测有向和无向图中的循环(可能有多少)。也就是说，代码应该适用于有向图和无向图。

使用 DFS 或拓扑排序 在各种帖子中大多被推荐。但在很大程度上，一切都针对无向图进行了处理。

This link描述了一种循环检测方法。据我了解，这适用于有向图。

This link有无向图中循环检测的代码。但我不明白它是如何忽略后缘的。也就是说，它必须忽略任何具有两个节点的循环，比如 D 到 C 和 C 到 D。 这意味着它必须在 DFS 递归时记住它的父级。但是代码似乎并没有解决这个问题。

欢迎提出任何建议..

Answer 1

首先，一些重要的方面: - 检测周期通常比计算它们更容易(因为你可以在另一个周期中有周期) - 事实上，对于有向图和无向图，算法可能非常不同(通常，对于无向图，算法效率更高)。

其次，我的通用算法(有向图的循环计数)的 2 美分将稍微修改 Floyd-Warshall algorithm :

for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            A[i][j] += A[i][k] * A[k][j];
        }
    }
}

上面的代码片段假设 A 是图形的邻接矩阵，n 是节点数。复杂度显然是 O(n^3)。

它将修改邻接矩阵以在每个位置 (i,j) 中包含从 i 开始到 j 结束的路径数。也就是说，如果你对以节点x开始的循环数感兴趣，就读A[x][x](矩阵主对角线的对应数)即可。

这里剩下的唯一问题是您是否对全局周期盘点感兴趣。由于我没有针对我想到的解决方案的正确性证明(并且没有时间验证它)，因此我不会发布任何详细信息(抱歉)。

---

PS:对于循环检测(仅)，有更快的选项可用:

• 在无向图中(最简单的情况)，尝试研究联合查找问题 (Disjoint set data structure)。这是我所知道的最快的非平凡图算法之一(如果我没记错的话，所有优化几乎是线性的)。

• 在有向图中，我会像您提到的那样使用 DFS。如果您在“dfs”函数中为“if (!marked[v])”添加一个 else(如:else 'a cycle was found')，您提到的第二个链接工作正常。