我看到了这篇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<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，然后去A -> C -> B，如果你不记得路径，你会认为有。
正如链接的帖子中所提到的，在返回代码之前，你可以将visited标志设置为false（我看到你现在已经这样做了）——这将起到记住路径的作用。
值得指出的是，该标记算法是对链表循环检测的天真方法的改编，该方法涉及跟踪到目前为止访问的每个节点。在这种情况下，递归所遵循的路径被视为链表，并应用链表算法。空间复杂性使得该算法对于链表来说是次优的，因为你需要保留对列表中每个节点的引用——它是O（n）。然而，当你把它应用于一个相当平衡的图时，空间复杂性会下降到O（logn）。在图是树的情况下，空间复杂度会降低到O（n），但时间复杂度会降到O（n）。
此外，该算法仍然不正确。给定具有节点A和B以及单个边缘B->B的图，isCyclicDirected(A)将永远不会检测到循环。
只有在图中没有通过两条不同路径从节点A到节点B的情况下，回溯才是必不可少的。在前面的回答中提到的情况下，您的算法将检测到假阳性：A->B\^v|C但是，如果你添加回溯，你的alto将完美工作，即使在上面的情况下。