查找图中的所有循环，还原 [英] Find all cycles in graph, redux

问题描述

我知道在这个问题上存在相当多的答案。然而，我发现他们中的任何一个都没有把它真正带到这个地步。

有人认为一个循环与强连通的组件（几乎）是一样的（查找有向图中的所有循环），因此可以使用为该目标设计的算法。

有些人认为找到 a 周期可以通过DFS完成，并检查后端边缘（对文件依赖性的boost图形文档）。


我现在想对图中的 all 周期是否可以通过DFS检测并检查后端边缘提供一些建议？

http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf （在这里找到）声明基于循环基础的一种方法。我个人，我不觉得它非常直观，所以我正在寻找一个不同的解决方案。



编辑：我的初步意见显然是错误的。 S.接下来的回答是Moron。


初始意见：
我认为它的确可以这样工作，因为DFS-VISIT（DFS的伪代码）刚刚进入每个节点那还没有去过。从这个意义上讲，每个顶点展现了一个循环的潜在开始。此外，由于DFS访问每个边缘一次，还会覆盖通往循环起点的每条边。因此，通过使用DFS和后端检查，确实可以检测图中的所有周期。请注意，如果存在具有不同参与节点数量的周期（例如三角形，矩形等），则需要做额外的工作来区分每个周期的形状。

解决方案

我已经完全回答了这个问题，所以请检查：

源排除排序总是会返回一个最大周期吗？

答案的相关部分：
$ b

对$ $进行深度优先搜索b $ b图。

您有兴趣识别返回的
边，即在遍历中，边
指向祖先（在
中是DFS树，这是由访问节点的
边缘访问节点导致的）。例如，如果DFS堆栈有节点
[A-> B-> C-> D]，并且在探索D
时找到了一条边D-> B，那就是后面
优势。每个后沿都定义一个周期。

更重要的是，由后缘引起的
周期是图的
周期的基本集合。 一个基本的
周期集合：您可以通过UNIONing和
基本集合的异或周期构造图形的所有周期
。以
为例，考虑周期
[A1-> A2-> A3-> A1]和
[A2-> B1-> B2-> B3-> A2]。你可以将
联合到循环中：
[A1-> A2-> B1-> B2-> B3-> A2-> A3-> A1]。

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:

Perform a Depth-First Search on your graph.

You are interested in recognizing back edges, i.e., in the traversal, an edge which points back to an ancestor (in the DFS tree, which is induced by edges of visiting nodes for the first time) of the visited node. For example, if the DFS stack has nodes [A->B->C->D] and while you explore D you find an edge D->B, that's a back edge. Each back edge defines a cycle.

More importantly, the cycles induced by back-edges are a basic set of cycles of the graph. "A basic set of cycles": you can construct all cycles of the graph just by UNIONing and XORing cycles of the basic set. For example, consider the cycles [A1->A2->A3->A1] and [A2->B1->B2->B3->A2]. You can union them to the cycle: [A1->A2->B1->B2->B3->A2->A3->A1].

这篇关于查找图中的所有循环，还原的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！