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.

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

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

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

如果你不能给节点添加一个“被访问过”的属性，使用一个集合(或者映射)，把所有被访问过的节点添加到集合中，除非它们已经在集合中。使用唯一的键或对象的地址作为“键”。

这还为您提供了关于循环依赖项的“根”节点的信息，当用户必须修复问题时，这些信息将派上用场。

另一个解决方案是尝试找到下一个要执行的依赖项。为此，您必须有一个可以记住您现在在哪里以及接下来需要做什么的堆栈。在执行依赖项之前，检查它是否已经在此堆栈上。如果是，你就找到了一个循环。

虽然这看起来可能有O(N*M)的复杂度，但你必须记住，堆栈的深度非常有限(所以N很小)，而且随着你可以检查为“已执行”的每个依赖项，M会变得越来越小，加上你可以在找到叶子时停止搜索(所以你永远不必检查每个节点-> M也会很小)。

在MetaMake中，我将图表创建为列表列表，然后在执行它们时删除每个节点，这自然地减少了搜索量。实际上，我从来不需要运行一个独立的检查，这一切都是在正常执行过程中自动发生的。

如果你需要一个“仅测试”模式，只需添加一个“干运行”标志，它禁止实际作业的执行。

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

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

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

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

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

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

如果一个图满足这个性质

|e| > |v| - 1

那么图至少包含一个周期。