2

我遇到了这篇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;
}
4

3 回答 3

5

为什么需要回溯：

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

如果你去A -> B而不回溯，你会停在那里，你不会找到循环。

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

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

A -> B
  \  ^
   v |
     C

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

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

于 2013-12-12T22:22:01.653 回答
1

值得指出的是，这种标记算法是对链表循环检测的朴素方法的改编，该方法涉及跟踪迄今为止访问的每个节点。在这种情况下，递归所遵循的路径被视为链表并应用链表算法。空间复杂度使算法对于链表来说不是最优的，因为你需要保存对链表中每个节点的引用，它是 O(n)。但是，当您将其应用于平衡良好的图形时，空间复杂度会降至 O(logn)。在图是一棵树的情况下，空间复杂度降低到 O(n)，但你得到 O(n) 时间复杂度。

此外，算法仍然不正确。给定一个带有节点A和B一条边的图B->B，isCyclicDirected(A)永远不会检测到循环。

于 2013-12-12T23:33:58.063 回答
0

仅当您的图表没有任何情况可以通过两条不同的路径从节点 A 到达节点 B 时，回溯才不是必需的。您的算法将在上一个答案中提到的情况下检测到误报：A -> B \ ^ v | C 但是，如果您添加回溯，您的中音将完美运行，即使在上述情况下也是如此。

于 2013-12-12T22:54:26.520 回答