有没有一种有效的算法来检测有向图中的循环?

我有一个有向图,表示需要执行的作业计划,作业是一个节点,依赖项是一个边。我需要检测这个图中导致循环依赖关系的循环的错误情况。


当前回答

There is no algorithm which can find all the cycles in a directed graph in polynomial time. Suppose, the directed graph has n nodes and every pair of the nodes has connections to each other which means you have a complete graph. So any non-empty subset of these n nodes indicates a cycle and there are 2^n-1 number of such subsets. So no polynomial time algorithm exists. So suppose you have an efficient (non-stupid) algorithm which can tell you the number of directed cycles in a graph, you can first find the strong connected components, then applying your algorithm on these connected components. Since cycles only exist within the components and not between them.

其他回答

我的方法是做一个拓扑排序,计算访问顶点的数量。如果这个数字小于DAG中的顶点总数,那么就有一个循环。

https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length我最喜欢这个解决方案,特别是4个长度:)

物理向导还说你必须做O(V^2)。我相信我们只需要O(V)/O(V+E)。 如果图是连通的,那么DFS将访问所有节点。如果图有连通的子图,那么每次我们在这个子图的顶点上运行DFS时,我们都会找到连通的顶点,并且不必为下一次运行DFS考虑这些。因此,对每个顶点运行的可能性是不正确的。

我已经在sml(命令式编程)中实现了这个问题。这是大纲。找到所有入度或出度为0的节点。这样的节点不能成为循环的一部分(因此将它们删除)。接下来,从这些节点中删除所有传入或传出边。 递归地将此过程应用于结果图。如果最后你没有剩下任何节点或边,图就没有任何循环,否则就有。

最简单的方法是对图进行深度优先遍历(DFT)。

如果图有n个顶点,这是一个O(n)时间复杂度算法。因为你可能必须从每个顶点开始进行DFT,所以总复杂度变成O(n^2)。

您必须维护一个包含当前深度第一次遍历的所有顶点的堆栈,其第一个元素是根节点。如果在DFT期间遇到一个元素已经在堆栈中,那么就有一个循环。

Tarjan的强连通分量算法的时间复杂度为O(|E| + |V|)。

有关其他算法,请参见维基百科上的强连接组件。