检测图中周期 [英] Detect cycles in graph
问题描述
可能重复：
的发现，图中的所有周期
有谁能够给我的教程，算法，...为检测周期图？
can anybody give me tutorial,algorithm,... for detect cycles in graph ?
我找到一些算法，并加以实施，但没有检测到所有周期
i find several algorithm and implement them but doesn't detect all cycles
strongly_connected_components_algorithm
推荐答案
从以上来看数学角度：
输入：图G =（V，E）
Input: Graph G=(V,E)
-
假设你的图形是不是不相交的（有每两个顶点之间存在路径）
Assume that your graph is not disjoint (there exists a path between every two vertices)
计算生成树图形的T（也有容易的算法做这一点）
Compute the spanning tree T of the graph (there are easy algorithms to do that)
让E'是E的一个子集，不属于生成树T.对于在电子商务各边e'，它除了树创建完全是一个单周期。让我们把所有这些周期为集合B。
Let E' be a subset of E, that don't belong to the spanning tree T. For each edge e in E', its addition to the tree creates exactly a single cycle. Let's put all those cycles into set B.
我们定义了一个双循环空间了在图形周期。在该空间中，两个周期可以增加。加入只是在边缘的独家总和。
We define a binary cycle space over cycles in your graph. In that space, two cycles can be added. The addition is simply an exclusive sum over the edges.
这组循环B是一个周期的基础。在图中每个周期可形成为周期的B的线性组合。
The set of cycles B is a "cycle basis". Every other cycle in your graph can be formed as a linear combination of the cycles B.
此方式，您获得您的图表中的所有可能的周期。
This way you obtain all possible cycles in your graph.
警告：：如果您的输入图形具有的 v 的顶点和电子的边缘则有2 ^（电子的 - v 的+1）-1不同的周期！这是相当多的 - 你可能不想明确写入所有的人
Warning: if your input graph has v vertices and e edges then there are 2^(e - v +1)-1 different cycles! That's quite a lot - you might not want to explicitly write all of them.
这篇关于检测图中周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
