查找图表中的所有周期,redux

Question

我知道这个问题有很多答案.但是,我发现它们中没有一个能够真正实现它.
有人认为一个循环(几乎)与强连通组件相同(s.在有向图中查找所有循环),因此可以使用为该目标设计的算法.
有人认为找到一个循环可以通过DFS完成并检查后端(s.文件依赖关系的boost图文档).

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

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

Answer 1

我已经彻底回答了这个问题,请检查一下:

源清除排序总是会返回最大循环吗？

答案的相关部分:

在图表上执行深度优先搜索.

您感兴趣的是识别后沿,即在遍历中,指向被访问节点的祖先(在DFS树中,由第一次访问节点的边缘引起)的边缘.例如,如果DFS堆栈有节点[A-> B-> C-> D],当您探索D时,您会发现边缘D-> B,这是一个后边缘.每个后边缘定义一个循环.

更重要的是,由后沿引起的周期是图的一组基本周期."一组基本循环":您可以通过基本集的UNIONing和XORing循环构建图的所有循环.例如,考虑循环[A1-> A2-> A3-> A1]和[A2-> B1-> B2-> B3-> A2].您可以将它们连接到循环:[A1-> A2-> B1-> B2-> B3-> A2-> A3-> A1].

Answer 2

如果遍历算法仅访问每条边一次，则它无法找到所有循环。一条边可以是多个周期的一部分。

顺便说一句，什么是后缘？

另外，也许你应该重新表述/格式化你的问题。这是非常难读的。