首页 文章

在有向图中使用DFS进行循环检测绝对需要回溯吗？

提问于
浏览 次
2

我遇到了这个SO post，其中建议在有向图中使用DFS进行循环检测由于回溯而更快 . 在这里，我引用该链接：

深度优先搜索比广度优先搜索更有效，因为您可以更快地回溯 . 如果使用调用堆栈，它也更容易实现，但这依赖于不会溢出堆栈的最长路径 . 此外，如果您的图表是定向的，那么您不仅要记住您是否访问过某个节点，还要记得您是如何到达那里的 . 否则你可能会认为你已经找到了一个循环，但实际上你所拥有的是两个独立的路径A-> B但这并不意味着存在路径B-> A.通过深度优先搜索，您可以在下降时将节点标记为已访问，并在您回溯时将其取消标记 .

为什么回溯必不可少？

有人可以用示例图解释给定 A->B 示例中的含义吗？

最后，我有一个 DFS 代码用于有向图中的循环检测，它不使用回溯但仍检测 O(E+V) 中的循环 .

public boolean isCyclicDirected(Vertex v){
  if (v.isVisited) {
    return true;
  }
  v.setVisited(true);
  Iterator<Edge> e = v.adj.iterator();
  while (e.hasNext()) {
    Vertex t = e.next().target;
    // quick test:
    if (t.isVisited) {
      return true;
    }
    // elaborate, recursive test:
    if (isCyclicDirected(t)) {
      return true;
    }
  }
  // none of our adjacent vertices flag as cyclic
  v.setVisited(false);
  return false;
}
algorithm depth-first-search backtracking directed-graph cyclic

3 回答

  • 5

    只有当您的图形没有任何情况可以通过两个不同的路径从节点A到达节点B时，回溯才是必不可少的 . 你的算法会在上一个答案中提到的情况下检测出误报：A - > B \ ^ v | C但是如果你添加回溯你的alto将完美地工作，即使在上面的情况下 .

    回复于
  • 1

    Why you need to backtrack:

    A -> B
^ \
|  v
D <- C

    如果你去 A -> B 并且你不会停在那里，你将找不到循环 .

    你的算法确实回溯了 . 你只是将它包装在递归中，所以它可能看起来不像你期望的那样 . 你为其中一个邻居递归，如果这没有找到一个循环，那个呼叫会返回并尝试其他邻居 - 这就是回溯 .

    Why you need to remember how you got to where you are:

    A -> B
  \  ^
   v |
     C

    上面的图表没有循环，但是如果你去 A -> B ，那么 A -> C -> B ，你就记住了路径 .

    如链接帖子中所述，您可以在返回代码之前将被访问标志设置为false（我看到您现在已经完成了） - 这将用作记住路径 .

    回复于
  • 0

    值得指出的是，这种标记算法是对链表循环检测的简单方法的改编，其涉及跟踪到目前为止所访问的每个节点 . 在这种情况下，递归后面的路径被视为链表，并应用链表算法 . 空间复杂性使得该算法对于链表而言是次优的，因为您需要对列表中的每个节点保持对O（n）的引用 . 当你将它应用于一个体面的 balancer 图时，空间复杂度下降到O（logn） . 在图形是树的情况下，空间复杂度降低到O（n），但是你得到O（n）时间复杂度 .

    此外，该算法仍然是不正确的 . 给定具有节点 A 和 B 以及单边 B->B 的图形， isCyclicDirected(A) 将永远不会检测到循环 .

    回复于

相关问题