有没有一种有效的算法来检测有向图中的循环?
我有一个有向图，表示需要执行的作业计划，作业是一个节点，依赖项是一个边。我需要检测这个图中导致循环依赖关系的循环的错误情况。
当前回答
如果一个图满足这个性质
|e| > |v| - 1
那么图至少包含一个周期。
其他回答
我的方法是做一个拓扑排序，计算访问顶点的数量。如果这个数字小于DAG中的顶点总数，那么就有一个循环。
假设这是一个作业时间表，我怀疑在某些时候您会将它们按照建议的执行顺序进行排序。
如果是这种情况，那么拓扑排序实现在任何情况下都可以检测到循环。UNIX tsort当然可以。因此，我认为在三步排序的同时检测循环比在单独的步骤中检测更有效。
因此，问题可能变成“我如何最有效地进行tsort”，而不是“我如何最有效地检测循环”。答案可能是“使用图书馆”，但如果没有下面的维基百科文章:
http://en.wikipedia.org/wiki/Topological_sorting
有一种算法的伪代码，以及来自Tarjan的另一种算法的简要描述。两者都具有O(|V| + |E|)时间复杂度。
在我看来，在有向图中检测周期最容易理解的算法是图着色算法。
基本上，图着色算法以DFS方式(深度优先搜索，这意味着它在探索另一条路径之前完全探索一条路径)遍历图。当它找到后边缘时，它将图形标记为包含循环。
有关图着色算法的深入解释，请阅读这篇文章:http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/
另外，我在JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js中提供了一个图形着色的实现
正如你所说，你有一组作业，它需要按一定的顺序执行。给定作业调度所需顺序的拓扑排序(如果是直接的非循环图，则用于解决依赖问题)。运行dfs并维护一个列表，并在列表的开头开始添加node，如果您遇到一个已经被访问过的节点。然后在给定的图中找到一个循环。
最简单的方法是对图进行深度优先遍历(DFT)。
如果图有n个顶点，这是一个O(n)时间复杂度算法。因为你可能必须从每个顶点开始进行DFT，所以总复杂度变成O(n^2)。
您必须维护一个包含当前深度第一次遍历的所有顶点的堆栈，其第一个元素是根节点。如果在DFT期间遇到一个元素已经在堆栈中，那么就有一个循环。
