有没有一种有效的算法来检测有向图中的循环?
我有一个有向图，表示需要执行的作业计划，作业是一个节点，依赖项是一个边。我需要检测这个图中导致循环依赖关系的循环的错误情况。
当前回答
我的方法是做一个拓扑排序，计算访问顶点的数量。如果这个数字小于DAG中的顶点总数，那么就有一个循环。
其他回答
在我看来，在有向图中检测周期最容易理解的算法是图着色算法。
基本上，图着色算法以DFS方式(深度优先搜索，这意味着它在探索另一条路径之前完全探索一条路径)遍历图。当它找到后边缘时，它将图形标记为包含循环。
有关图着色算法的深入解释，请阅读这篇文章:http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/
另外，我在JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js中提供了一个图形着色的实现
https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length我最喜欢这个解决方案，特别是4个长度:)
物理向导还说你必须做O(V^2)。我相信我们只需要O(V)/O(V+E)。 如果图是连通的，那么DFS将访问所有节点。如果图有连通的子图，那么每次我们在这个子图的顶点上运行DFS时，我们都会找到连通的顶点，并且不必为下一次运行DFS考虑这些。因此，对每个顶点运行的可能性是不正确的。
如果一个图满足这个性质
|e| > |v| - 1
那么图至少包含一个周期。
Tarjan的强连通分量算法的时间复杂度为O(|E| + |V|)。
有关其他算法，请参见维基百科上的强连接组件。
从DFS开始:当且仅当DFS期间发现后边缘时，循环存在。这是白径定理的结果。
