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

问题描述

我知道这个问题有很多答案.但是，我发现他们中没有一个人真正切中要害.
有些人认为循环(几乎)与强连接组件相同(s. 在有向图中查找所有循环)，因此可以使用为该目标设计的算法.
一些人认为，可以通过 DFS 并检查后缘来找到一个循环(s.关于文件依赖关系的增强图文档).

我现在想就是否可以通过 DFS 检测图中的所有循环并检查后边缘提出一些建议?
http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf(在此处找到 SO)陈述了一种基于循环基础的方法.就我个人而言，我觉得它不是很直观，所以我正在寻找不同的解决方案.

我最初的意见显然是错误的.S.白痴"的下一个答案.
初步意见:我的观点是，它确实可以这样工作，因为 DFS-VISIT(DFS 的伪代码)刚刚进入尚未访问的每个节点.从这个意义上说，每个顶点都表现出一个循环的潜在开始.此外，由于 DFS 访问每条边一次，因此也涵盖了通向循环起点的每条边.因此，通过使用 DFS 和后端检查，确实应该可以检测图中的所有循环.请注意，如果存在具有不同数量参与者节点的循环(例如三角形、矩形等)，则必须做额外的工作来区分每个循环的实际形状".

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.

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:

将删除源代码排序总是返回一个最大循环?

答案的相关部分:

对您的数据执行深度优先搜索图表.

Perform a Depth-First Search on your graph.

您有兴趣识别回来边，即在遍历中，边它指向一个祖先(在DFS 树，由第一个访问节点的边时间)被访问节点.为了例如，如果 DFS 堆栈有节点[A->B->C->D] 当你探索 D你找到一条 D->B 边，那是一条背边缘.每个后缘定义一个循环.

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.

更重要的是，周期诱导by back-edges 是一组基本的图的循环.一套基本的循环":您可以构建所有循环仅通过 UNIONing 和基本集合的异或循环.为了例如，考虑周期[A1->A2->A3->A1] 和[A2->B1->B2->B3->A2].你可以联合他们进入循环:[A1->A2->B1->B2->B3->A2->A3->A1].

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].

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