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

我发现了这篇SO帖子,建议在有向图中使用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 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
  \  ^
   v |
     C