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.

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

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

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

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

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

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

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

在我看来，在有向图中检测周期最容易理解的算法是图着色算法。

基本上，图着色算法以DFS方式(深度优先搜索，这意味着它在探索另一条路径之前完全探索一条路径)遍历图。当它找到后边缘时，它将图形标记为包含循环。

有关图着色算法的深入解释，请阅读这篇文章:http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

另外，我在JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js中提供了一个图形着色的实现

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

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

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