检测周期在图

可能重复：
Finding all cycles in graph 检测周期在图

有谁能够给我的教程，算法，...在图中检测周期？

我发现几个算法并加以实施，但没有检测到所有周期

2011-03-01 SajjadZare

我想那里的问题，虽然mared作为“回答”它没有正确回答。 – CygnusX1 2011-03-01 21:23:48

@Cygn这不是允许dups的理由。只要去那里，通过发表意见来“加热”这个问题，说明 – 2011-03-01 22:22:09

有一个实现来检测名为'networkx'的python库中的图中的所有周期。 **这真的很简单！** 我在下面的帖子中给出了详细的答案：http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph/33956957#33956957 – fernandosjp 2016-10-28 14:18:10

从视图多个数学点：

输入：图形G =（V，E）

假设你的图形是不相交（有每两个顶点之间存在路径）
计算spanning tree T中的曲线图的（有容易的算法来做到这一点）
令E”是的一个子集E，它们不属于生成树T.对于E'中的每个边e，它对树的添加只产生一个单独的循环。让我们把所有这些循环置于集合B中。
我们在图中定义了一个binary cycle space循环。在该空间中，可以添加两个循环。加法仅仅是边缘上的独占总和。
循环组B是一个“循环基础”。在图形中，每隔一个周期可以形成为周期的线性组合B.

这样，你在你的图获得所有可能的周期。

警告：如果输入图有v顶点和Ë边缘则有2 ^（Ë - v +1）-1不同的周期！这相当多 - 你可能不想明确地写出所有这些。

来源

2011-03-01 21:11:59 CygnusX1

-2

我认为DFS会做你的工作怎么把我们纪念访问节点，如果我们发现该节点再有一个周期

来源

2011-03-01 14:28:59 ashmish2

这种方法是不正确的。就拿这个例子 '1 - > 2 2 - > 3 1 - > 3' 现在，在这种情况下，我们做的DFS（1）。这将会调用dfs（2）并将2标记为已访问。这将调用dfs（3）并将3标记为已访问。现在DFS（3）将再次从节点1调用，因为它已经访问了，你会错误地推断，它的一个周期 – 2012-04-03 12:16:58

A BFS alg。也没关系。我相信它比DFS更容易实现，因为它将访问/访问节点保持在队列中。检查某个节点是否已经访问过很容易。

来源

2011-03-01 19:51:46

检测周期在图

回答

相关问题