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

我遇到了这个SO post https://stackoverflow.com/questions/2869647/why-dfs-and-not-bfs-for-finding-cycle-in-graphs其中建议由于回溯，在有向图中使用 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;
}

为什么需要回溯：

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

如果你走的话A -> B如果你不回头，你就会停在那里，找不到循环。

你的算法确实会回溯。您只是将其包装在递归中，因此它可能看起来不太像您期望的那样。您对其中一个邻居进行递归，如果找不到循环，则该调用返回并尝试其他邻居 - 这就是回溯。

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

A -> B
  \  ^
   v |
     C

上图没有循环，但是如果你去A -> B, then A -> C -> B，如果你不记得路径，你会认为有。

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