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

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

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

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

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

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

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

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

如果一个图满足这个性质

|e| > |v| - 1

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

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

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