单一算法在定向和非定向图上工作以检测周期？

我一直在试图实现一个算法来检测周期（可能有多少）在directed and undirected graph。这是代码应该适用于有向图和无向图。单一算法在定向和非定向图上工作以检测周期？

使用DFS or topological sort主要推荐在各种职位。但很大程度上，所有内容都是针对无向图。

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

This link在无向图中具有循环检测的代码。但我不明白它是如何忽略后端的。那就是它必须忽略任何有两个节点的循环，比如D到C和C到D. 这意味着它必须在DFS递归时记住它。但代码似乎没有考虑到这一点。

任何建议，欢迎..

enter image description here

来源

2013-11-26 brain storm

您的第二个链接是关于检测** Connected Component **，而不是关于周期。 – justhalf

不是连接组件基本上是一个循环？ –

一个循环是k个顶点的子图，其中有'k'个边将'k'个顶点连接成一个循环。连通分量是连接的k个顶点的诱导子图。在你的图例中，只有一个连通分量（整个图），并且有三个循环：'A-B-E-A'，'A-B-D-A'，'A-E-B-D-A'。 – justhalf

首先，一些重要的方面： - 检测周期通常比它们的计数（因为你可以有另一个周期内周期）更容易 - 事实上，用于定向和无向图，算法可能会非常不同（通常，对于无向情况来说效率更高）。

其次，我的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找到了一个循环）。

来源

2013-11-26 04:30:17

单一算法在定向和非定向图上工作以检测周期？

回答

相关问题