问题描述
我知道在这个问题上存在相当多的答案。然而,我发现他们中的任何一个都没有把它真正带到这个地步。
有人认为一个循环与强连通的组件(几乎)是一样的(),因此可以使用为该目标设计的算法。
有些人认为找到 a 周期可以通过DFS完成,并检查后端边缘(对文件依赖性的boost图形文档)。
我现在想对图中的 all 周期是否可以通过DFS检测并检查后端边缘提供一些建议?
(在这里找到)声明基于循环基础的一种方法。我个人,我不觉得它非常直观,所以我正在寻找一个不同的解决方案。
编辑:我的初步意见显然是错误的。 S.接下来的回答是Moron。
初始意见:
我认为它的确可以这样工作,因为DFS-VISIT(DFS的伪代码)刚刚进入每个节点那还没有去过。从这个意义上讲,每个顶点展现了一个循环的潜在开始。此外,由于DFS访问每个边缘一次,还会覆盖通往循环起点的每条边。因此,通过使用DFS和后端检查,确实可以检测图中的所有周期。请注意,如果存在具有不同参与节点数量的周期(例如三角形,矩形等),则需要做额外的工作来区分每个周期的形状。
我已经完全回答了这个问题,所以请检查:
答案的相关部分:
$ b
I know there are a quite some answers existing on this question. However, I found none of them really bringing it to the point.
Some argue that a cycle is (almost) the same as a strongly connected components (s. Finding all cycles in a directed graph) , so one could use algorithms designed for that goal.
Some argue that finding a cycle can be done via DFS and checking for back-edges (s. boost graph documentation on file dependencies).
I now would like to have some suggestions on whether all cycles in a graph can be detected via DFS and checking for back-edges?
http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf (found here on S.O.) states one methode based on cycle bases. Me personally, I don't find it very intuitive so I'm looking for a different solution.
EDIT: My initial opinion was apparently wrong. S. next answer by "Moron".
Initial opinion:My opinion is that it indeed could work that way as DFS-VISIT (s. pseudocode of DFS) freshly enters each node that was not yet visited. In that sense, each vertex exhibits a potential start of a cycle. Additionally, as DFS visits each edge once, each edge leading to the starting point of a cycle is also covered. Thus, by using DFS and back-edge checking it should indeed be possible to detect all cycles in a graph. Note that, if cycles with different numbers of participant nodes exist (e.g. triangles, rectangles etc.), additional work has to be done to discriminate the acutal "shape" of each cycle.
I have already answered this thoroughly, so check this:
Will a source-removal sort always return a maximal cycle?
The relevant part of the answer:
这篇关于查找图中的所有循环,还原的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!