从DFS开始:当且仅当DFS期间发现后边缘时，循环存在。这是白径定理的结果。

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

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

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

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

如果一个图满足这个性质

|e| > |v| - 1

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

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示例中的后边缘。

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

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