问题描述
我知道在这个问题上存在相当多的答案。然而，我发现他们中的任何一个都没有把它真正带到这个地步。
有人认为一个循环与强连通的组件（几乎）是一样的（），因此可以使用为该目标设计的算法。
有些人认为找到 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:
这篇关于查找图中的所有循环，还原的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！