正如你所说，你有一组作业，它需要按一定的顺序执行。给定作业调度所需顺序的拓扑排序(如果是直接的非循环图，则用于解决依赖问题)。运行dfs并维护一个列表，并在列表的开头开始添加node，如果您遇到一个已经被访问过的节点。然后在给定的图中找到一个循环。

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

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

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

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

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

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

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

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

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

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

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

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