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

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


当前回答

如果DFS发现一条边指向一个已经访问过的顶点,那么这里就有一个循环。

其他回答

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

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

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

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

正如你所说,你有一组作业,它需要按一定的顺序执行。给定作业调度所需顺序的拓扑排序(如果是直接的非循环图,则用于解决依赖问题)。运行dfs并维护一个列表,并在列表的开头开始添加node,如果您遇到一个已经被访问过的节点。然后在给定的图中找到一个循环。

如果DFS发现一条边指向一个已经访问过的顶点,那么这里就有一个循环。

假设这是一个作业时间表,我怀疑在某些时候您会将它们按照建议的执行顺序进行排序。

如果是这种情况,那么拓扑排序实现在任何情况下都可以检测到循环。UNIX tsort当然可以。因此,我认为在三步排序的同时检测循环比在单独的步骤中检测更有效。

因此,问题可能变成“我如何最有效地进行tsort”,而不是“我如何最有效地检测循环”。答案可能是“使用图书馆”,但如果没有下面的维基百科文章:

http://en.wikipedia.org/wiki/Topological_sorting

有一种算法的伪代码,以及来自Tarjan的另一种算法的简要描述。两者都具有O(|V| + |E|)时间复杂度。