我碰到这个 SO发布其中，因此建议有向图使用DFS更快，因为回溯的周期检测。在这里，我从这个链接引用：

深度优先搜索比广度优先搜索更高效的内存，你可以原路返回越快。它也更容易，如果你使用调用栈来实现，但这种依赖的最长路径上没有溢出堆栈。

另外，如果你的图是针对，那么你必须不只是记住       如果你曾经访问过一个节点或没有，还怎么你到了那里。       否则，你可能会认为你已经找到了一个周期，但在现实中       你已经是两个独立的路径A-> B，但是，这并不意味着       有一条小路B-> A。随着深度优先搜索，你可以标记节点       只要您下降和取消标记他们为您跟踪访问。

为什么回溯本质？

有人可以用一​​个例子图的是什么意思，在解释给定的 A-＆GT; B 例如

最后，我有向图一个 DFS code为周期检测不使用回溯，但仍检测周期 O（ E + V）。

解决方案

为什么你需要回溯：

  A  - ＆GT;乙
^ \
| v
D＆LT;  - Ç
 

如果你去 A - ＆GT;乙，你不走回头路，你会停在那里，你将找不到循环。

您的算法并原路返回。你只是包装在递归所以它可能不是很期待您预期的方式。你递归的邻居之一，如果没有找到一个循环，即调用返回，并尝试一些其他的邻居 - 这是回溯

为什么你要记住，你是怎么到你在哪里：

  A  - ＆GT;乙
  \ ^
   V |
     C
 

上图没有周期，但如果你去 A - ＆GT;乙，然后 A - ＆GT; C - ＆GT;乙，你会觉得，如果你不记得路径存在。

正如链接后，你可以设置访问标志设置为false在code回来（我看你现在已经完成）之前 - 这将作为记忆的路径

I came across this SO post where it is suggested that cycle detection using DFS in a directed graph is faster because of backtracking. Here I quote from that link:

Depth first search is more memory efficient than breadth first search as you can backtrack sooner. It is also easier to implement if you use the call stack but this relies on the longest path not overflowing the stack.

Also if your graph is directed then you have to not just remember if you have visited a node or not, but also how you got there. Otherwise you might think you have found a cycle but in reality all you have is two separate paths A->B but that doesn't mean there is a path B->A. With a depth first search you can mark nodes as visited as you descend and unmark them as you backtrack.

Why is backtracking essential?

Can someone explain with an example graph as what is meant in the given A->B example?

Finally, I have a DFS code for cycle detection in directed graph that does not use backtracking but still detects cycle in 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;
}

Why you need to backtrack:

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

If you go A -> B and you don't backtrack, you'll stop there and you won't find the cycle.

Your algorithm does backtrack. You're just wrapping it in recursion so it might not quite look the way you expect. You recurse for one of the neighbours, if this doesn't find a cycle, that call returns and you try some other neighbour - this is backtracking.

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

A -> B
  \  ^
   v |
     C

The above graph has no cycle, but if you go A -> B, then A -> C -> B, you'll think there is if you don't remember the path.

As mentioned in the linked post, you can just set the visited flag to false before returning in your code (which I see you've now done) - this will act as remembering the path.