cycle - 如何使用拓扑排序在有向图中找到循环？

Question

我在我的程序中实现了这个伪代码来检查有向图是否是非循环的:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

这很好用，但如果图形不是非循环的，我还需要输出实际的循环。是否可以在这段代码“内部”执行此操作，或者我是否需要完全更改我的算法？我试图寻找解决方案，并找到了这个答案 ( Printing(not detecting) cycle with topological sort )，但我不明白如何实际执行此操作。有没有人有一些可以帮助我的伪代码？

Answer 1

首先，您尝试做的事情有点问题，因为可能存在多个循环。理论上，图中的每个节点都可以有一条自指向边，那么就有n个圈。

但是，一种简单的方法是捕获图中的任何边，然后对其进行迭代，直到返回到相同的边，然后将其作为循环输出。应删除导致死胡同的边，并且发现的任何循环也应从图中删除所有循环边。继续这样做，直到图形没有更多的边，这应该输出图形中的所有循环，尽管没有特定的顺序或优化，如果按特定顺序执行，可能会错过一些循环。