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

Question

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

深度优先搜索比广度优先搜索更节省内存，因为您可以更快地回溯。如果使用调用堆栈，则实现起来也更容易，但这取决于不溢出堆栈的最长路径。

如果你的图是有方向的，那么你不仅要记住你是否访问过一个节点，还要记住你是如何到达的。否则，你可能会认为你已经找到了一个循环，但在现实中，你所拥有的只是两条不同的路径-

为什么回溯是必要的？

有人能用示例图解释一下给定A中的含义吗-

最后，我有一个用于有向图中循环检测的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;
}




Answer 1

只有当您的图没有任何可以通过两条不同路径从节点A到节点B的情况下，回溯才是必要的。你的算法将检测到一个假阳性的情况下，提到在前面的答案：A-

Answer 2

值得指出的是，这种标记算法是对链表周期检测的朴素方法的一种改进，这种方法涉及到跟踪到目前为止访问的每个节点。在这种情况下，递归后的路径被视为链表，并应用链表算法。对于链表来说，空间复杂度是算法次优的原因，因为您需要保持对列表中每个节点的引用，它是O（n）。然而，当你把它应用到一个相当平衡的图上时，空间复杂度下降到O（logn）。在图是树的情况下，空间复杂度降低为O（n），但时间复杂度为O（n）。

此外，算法仍然不正确。给定一个具有节点a和B以及单条边B的图-

Answer 3

您需要回溯的原因：

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

如果你去A-

你的算法会回溯。您只是用递归包装它，所以它可能看起来不太像您期望的那样。你递归为一个邻居，如果这没有找到一个循环，那个调用返回，你尝试其他邻居——这是回溯。

为什么你需要记住你是如何到达现在的位置的：

A -> B
  \  ^
   v |
     C

上图没有循环，但是如果你去A-

正如链接文章中提到的，在返回代码之前，您可以将访问标志设置为false（我看到您现在已经这样做了）——这将起到记住路径的作用。