algorithm - 单一算法可同时用于有向图和无向图以检测周期？

我一直在尝试实现一种算法来检测directed and undirected graph中的周期（可能有多少个周期）这就是代码应该同时适用于有向图和无向图。
在不同的岗位上，推荐使用DFS or topological sort但在很大程度上，一切都是针对无向图的。
This link描述了一种循环检测方法。据我所知，这适用于有向图。
This link具有无向图中循环检测的代码但我不明白它是怎么忽略了后缘的。也就是说，它必须忽略具有两个节点的任何循环，比如d到c和c到d。
这意味着当DFS递归时，它必须记住它的父级但代码似乎没有考虑到这一点。
欢迎提出任何建议。

最佳答案

首先，一些重要方面：
-检测周期通常比计数容易（因为你可以在另一个周期中有周期）
-实际上，对于有向图和无向图，算法可能非常不同（通常，对于无向图，算法效率更高）。
其次，我对通用算法（有向图的循环计数）的2美分将稍作修改：

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开始的循环数感兴趣，只需读取[x][x]（矩阵主对角线的对应数）。
唯一的问题是如果你对全球周期计数感兴趣。由于我没有一个正确的解决方案的证据，我在脑海中（并没有时间验证它），我不会张贴任何细节（抱歉）。
PS：对于循环检测（仅限），有更快的选项可供选择：
在无向图（最简单的情况）中，尝试研究联合查找问题（Floyd-Warshall algorithm）。这是我知道的最快的非平凡图算法之一（如果我没记错的话，几乎与所有的优化都是线性的）。
在有向图中，我将使用您提到的DFS你提到的第二个链接如果你在“if”（！在“dfs”函数中标记了“[v]）”（如：else'a cycle was found'）。

关于algorithm - 单一算法可同时用于有向图和无向图以检测周期？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20206162/