首页 文章

在可能未连接的有向图中找到循环的混淆

提问于
浏览 次
1

我很困惑这个answer . 为什么DFS在访问每个节点和每个边缘最多一次时无法确定有向图中是否存在循环？使用white, gray, black方法，如果存在后沿，则应该能够找到循环 .

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

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

“可以在没有循环存在的情况下在DFS中多次访问节点”

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

我错过了什么？

Update and conclusions:

根据Pham Trung的评论，看起来该答案中的“简单DFS”是指从强连接图中的一个节点开始的DFS . 据我了解，对于图表可能未连接的一般情况，以下语句应为真：

  • 使用DFS并从未连接图中的任意未访问节点开始，确实可以多次访问每个节点，但是将使用白灰黑色着色，一个循环 - 如果存在 - 将被正确找到 .

  • 这样的DFS算法的运行时间是 O(d.|V|+|E|) ，其中 d 是所有节点中的最大度数（即我们可以使用这种基于DFS的算法访问每个节点的最大时间）

  • 而且，正如这个other answer建议的那样，如果在探索 O(|V|) 边后，找不到一个循环，它就不存在了 . 所以运行时真的是 O(|V|) .

algorithm graph computer-science directed-graph

1 回答

  • 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的回答意味着 simple depth-first-search 是一个正常的原始DFS（仅检查连接的组件） . 在同一个答案中，他还描述了如何修改 simple DFS 以找到循环的存在，这正是OP引用的算法 . 在下面，另一个答案也提到了着名的书中的引理

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

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

    回复于

相关问题