algorithm - 在可能不连通的有向图中寻找循环的困惑

Question

我对此感到困惑answer .为什么DFS不能在有向图中最多访问每个节点和每个边一次时判断是否有环？使用 white, gray, black方法，如果有向后的边缘，应该能够找到一个循环。

对于未连接的有向图，为什么不能执行以下操作:从任意节点 v 运行 DFS 并访问与 v 连接的节点一样多的节点，然后在图中另一个未访问的任意节点(如果有的话)上运行 DFS，直到访问所有节点？

在我看来，DFS 应该能够找到一个循环，如果它存在于至多 o(|V|+|E|) 时间。此声明是否在 above mentioned answer 中？错误的？

"It is possible to visit a node multiple times in a DFS without a cycle existing"

此外，因为这个other answer建议，如果循环存在，DFS 应该在探索最大 |V| 边后找到它，因此运行时间实际上是 O(|V|)。

我错过了什么？

更新和结论:

根据 Pham Trung 的评论，该答案中的“简单 DFS”似乎是指从强连通图中的一个节点开始的 DFS。据我了解，对于图可能未连接的一般情况，以下陈述应该是正确的:

• 使用 DFS 并从未连接图中的任意未访问节点开始，确实每个节点可能被访问不止一次，但使用白-灰-黑着色，将正确找到循环 - 如果存在 - 。
• 这种 DFS 算法的运行时间是 O(d.|V|+|E|)，其中 d 是所有节点中的最大入度(即我们可以使用这种基于 DFS 的算法访问每个节点的最长时间)
• 此外，因为这个other answer建议，如果在探索 O(|V|) 边之后，没有找到环，则它不存在。所以运行时实际上是 O(|V|)。

Answer 1

想象一下，我们有这个带有这些边的简单图:

• 1 -> 3

• 2 -> 3

  1 ----->3
          ^
          |
  2--------
  

所以，在我们的第一个dfs中，我们发现了节点1和3。然后，我们继续对节点2进行dfs，现在，我们又遇到了节点3，但这是一个循环吗？显然不是。

再举一个例子:

• 1 -> 3

• 1 -> 2

• 2 -> 3

  1----->3
  |      ^
  |      |
  |      |
  v      |
  2-------
  

所以，从节点 1 开始，我们访问节点 3，回到节点 2，现在，我们再次遇到节点 3，并且，这种情况，它也不是一个循环。

据我了解，Jay Conrod 的回答中的简单深度优先搜索 是指正常的原始 DFS(仅检查连通分量)。在同一个答案中，他还描述了如何修改simple DFS 来找到循环的存在，这正是OP引用的算法。而在下面，另一个答案也提到了著名的算法导论一书中的引理

A directed graph G is acyclic if and only if a depth-first search of G yields no back edges

总之，OP对检测有向图中环的理解是正确的，只是一些复杂性和捷径导致了误解。