在可能不连通的有向图中寻找循环的混淆

提问者：小点点

我对这个答案感到困惑。为什么DFS不能在最多访问一次有向图的每个节点和每条边的同时决定有向图中是否存在循环？使用白、灰、黑方法，如果有后向边，应该能够找到循环。

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

在我看来，DFS应该能够找到一个循环，如果它最多存在于o（|V||E|）时间。上面提到的答案中的这个说法是错误的吗？

msgstr"可以在一个DFS中多次访问一个节点而不存在循环"

此外，正如另一个答案所暗示的，如果循环存在，DFS应该在探索最多的|V|边后找到它，所以运行时实际上是O（|V|）。

我错过了什么？

更新和结论：

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

共1个答案

匿名用户

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

1 -

2 -

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

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

再举一个例子：

1 -

2 -

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

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

据我所知，杰伊·康罗德的答案中简单的深度优先搜索意味着，一个正常的、原始的DFS（只检查连接的分量）。在同一个答案中，他还描述了如何修改简单的DFS来找到循环的存在，这正是OP引用的算法。就在下面，另一个答案也提到了著名的算法导论书中的一个引理

有向图G是无环的当且仅当G的深度优先搜索没有返回边

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