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.

根据Cormen et al.， Introduction to Algorithms (CLRS)引理22.11:

有向图G是无环的当且仅当深度优先搜索G没有得到后边。

在几个回答中已经提到了这一点;在这里，我还将提供一个基于CLRS第22章的代码示例。示例图如下所示。

CLRS深度优先搜索的伪代码如下:

在CLRS图22.4中的示例中，图由两棵DFS树组成:一棵由节点u、v、x和y组成，另一棵由节点w和z组成。每棵树都包含一条后边:一条从x到v，另一条从z到z(一个自循环)。

关键的实现是，在DFS-VISIT函数中，当在u的邻居v上迭代时，遇到一个带有灰色的节点时，就会遇到后边缘。

下面的Python代码是CLRS伪代码的改编，添加了一个if子句，用于检测周期:

import collections


class Graph(object):
    def __init__(self, edges):
        self.edges = edges
        self.adj = Graph._build_adjacency_list(edges)

    @staticmethod
    def _build_adjacency_list(edges):
        adj = collections.defaultdict(list)
        for edge in edges:
            adj[edge[0]].append(edge[1])
            adj[edge[1]] # side effect only
        return adj


def dfs(G):
    discovered = set()
    finished = set()

    for u in G.adj:
        if u not in discovered and u not in finished:
            discovered, finished = dfs_visit(G, u, discovered, finished)


def dfs_visit(G, u, discovered, finished):
    discovered.add(u)

    for v in G.adj[u]:
        # Detect cycles
        if v in discovered:
            print(f"Cycle detected: found a back edge from {u} to {v}.")
            break

        # Recurse into DFS tree
        if v not in finished:
            dfs_visit(G, v, discovered, finished)

    discovered.remove(u)
    finished.add(u)

    return discovered, finished


if __name__ == "__main__":
    G = Graph([
        ('u', 'v'),
        ('u', 'x'),
        ('v', 'y'),
        ('w', 'y'),
        ('w', 'z'),
        ('x', 'v'),
        ('y', 'x'),
        ('z', 'z')])

    dfs(G)

注意，在本例中，CLRS伪代码中的时间没有被捕获，因为我们只对检测周期感兴趣。还有一些样板代码，用于从边列表构建图的邻接表表示。

当这个脚本执行时，它输出如下:

Cycle detected: found a back edge from x to v.
Cycle detected: found a back edge from z to z.

这些正是CLRS图22.4示例中的后边缘。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如果一个图满足这个性质

|e| > |v| - 1

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