在可能不相关的有向图中找到一个循环的困惑 [英] Confusions on finding a cycle in a possibly unconnected directed graph

问题描述

我对这个答案感到困惑。为什么DFS无法确定在有向图中是否有循环访问每个节点和每条边时最多只有一次？使用白色，灰色，黑色方法，应该如果存在后向边缘，则可以找到一个循环。

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

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

可以在没有
周期的情况下在DFS中多次访问节点

此外，正如其他答案所示，如果一个循环存在，DFS应该在探索最大值 | V | 边缘后找到它，所以运行时间确实是 O（| V |）。

我错过了什么？

更新和结论：

基于Pham Trung的评论，它看起来像该答案中的简单DFS是指从强连通图中的一个节点开始的DFS。据我了解，对于图表可能没有连接的一般情况，下面的语句应该是正确的：

• 使用DFS并从一个任意未访问的节点在一个未连接的图中，确实每个节点都可能被访问多次，但使用白色 - 黑色 - 着色，周期 - 如果存在 - 将正确找到。


• 这种DFS算法的运行时间是 O（d。| V | + | E |），其中 d 是所有节点中的最大进入度（即，我们可以使用这种基于DFS的算法访问每个节点的最大时间）
  
• 此外，由于其他答案建议，如果在探索 O（| V |）边缘之后，没有找到，它不存在。所以运行时真的是 O（| V |）。

解决方案

想象一下，我们有这样一个简单的图形：

• <1> - > 3
  >


• <2> - > 3

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

$ b $因此，在我们的第一个dfs中，我们发现节点1和3.并且，我们继续对节点2执行dfs，现在我们再次遇到节点3，但是这是一个循环吗？显然不是。

再举一个例子：

• 1 - > 3




• 1 - > 2

b
$ b

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

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

据我所知，Jay Conrod的答案中的简单深度优先搜索意味着一个正常的原始DFS（仅用于检查连接组件）。在同样的答案中，他还介绍了如何修改简单的DFS 来查找循环的存在，这正是OP引用的算法。下面，另一个答案也提到了着名的算法介绍 book

有向图G是非循环的当且仅当G的深度优先搜索不产生后沿时

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

I am confused about this answer. Why can't DFS decide if there is a cycle in a directed graph while visiting each node and each edge at most once? Using the white, gray, black method, one should be able to find a cycle if there is a backward edge.

For an unconnected directed graph, why can't one do the following: run DFS from an arbitrary node v and visit as many nodes as v is connected to, then run DFS on another unvisited arbitrary node in the graph, if any, until all nodes are visited?

It seems to me that DFS should be able to find a cycle if it exists in at most o(|V|+|E|) time. Is this claim in the above mentioned answer wrong?

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

Moreover, as this other answer suggest, if a cycle exists, DFS should find it after exploring a maximum of |V| edges, so the run time is really O(|V|).

What am I missing?

Update and conclusions:

Based on Pham Trung's comments, it looks like the "simple DFS" in that answer refers to a DFS starting from one node in a strongly connected graph. As I understand it, for a general case that the graph might be unconnected, the following statements should be true:

• Using DFS and starting from an arbitrary unvisited node in an unconnected graph, it is true that each node might be visited more than once, but using white-gray-black coloring, a cycle -if exists - will be correctly found.
• The run time of such a DFS algorithm is O(d.|V|+|E|), where d is the max in-degree among all nodes (i.e. the max time that we can visit each node using such DFS-based algorithm)
• Moreover, as this other answer suggest, if after exploring O(|V|) edges, a cycle was not found, it does not exist. So the runtime is really O(|V|).

解决方案

Imagine we have this simple graph with these edges:

• 1 -> 3

• 2 -> 3

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

So, in our first dfs, we discover node 1 and 3. And, we continue to do dfs with node 2, now, we encounter node 3 again, but is this a cycle? obviously not.

One more example:

• 1 -> 3

• 1 -> 2

• 2 -> 3

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

So, starting with node 1, we visit node 3, back to node 2, and now, we encounter node 3 one more time, and, this case, it is not a cycle also.

As far as I understand the simple depth-first-search from Jay Conrod's answer means, a normal, original DFS (only checking for connected component). In the same answer, he also described how to modify simple DFS to find the existence of cycle, which is exactly the algorithm OP has cited. And right below, another answer also mentioned a lemma in the famous Introduction to algorithm book

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

In short, OP's understanding to detect cycle in directed graph is correct, it is just some complexities and shortcuts have lead to misunderstanding.

这篇关于在可能不相关的有向图中找到一个循环的困惑的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！