98

DFS 主要用于在图中找到循环，而不是 BFS。有什么理由吗？两者都可以在遍历树/图时查找节点是否已被访问。

4

10 回答 10

84

深度优先搜索比广度优先搜索更节省内存，因为您可以更快地回溯。如果您使用调用堆栈也更容易实现，但这依赖于最长的路径不会溢出堆栈。

此外，如果您的图表是定向的，那么您不仅要记住您是否访问过某个节点，还要记住您是如何到达那里的。否则你可能会认为你找到了一个循环，但实际上你只有两条独立的路径 A->B，但这并不意味着有一条路径 B->A。例如，

如果您从 开始执行 BFS 0，它将检测到存在循环，但实际上没有循环。

通过深度优先搜索，您可以在下降时将节点标记为已访问，并在回溯时取消标记它们。有关此算法的性能改进，请参阅评论。

对于在有向图中检测循环的最佳算法，您可以查看Tarjan 的算法。

于 2010-05-19T21:44:45.090 回答
31
  1. DFS 更容易实现
  2. 一旦 DFS 找到一个循环，堆栈将包含形成循环的节点。BFS 并非如此，因此如果您还想打印找到的循环，则需要做额外的工作。这使得 DFS 更加方便。
于 2010-05-19T21:51:24.560 回答
13

如果图是无向的，则 BFS 可能是合理的（作为我的客人展示使用 BFS 的有效算法，该算法将报告有向图中的循环！），其中每个“交叉边”定义一个循环。如果交叉边是{v1, v2}，并且包含这些节点的根（在 BFS 树中）是r，那么循环是r ~ v1 - v2 ~ r（~是路径，-单边），这几乎可以像在 DFS 中一样容易地报告。

使用 BFS 的唯一原因是，如果您知道您的（无向）图将有长路径和小路径覆盖（换句话说，又深又窄）。在这种情况下，BFS 的队列需要的内存比 DFS 的堆栈要少（当然两者仍然是线性的）。

在所有其他情况下，DFS 显然是赢家。它适用于有向图和无向图，并且报告循环很简单——只需将任何后边连接到从祖先到后代的路径，就可以得到循环。总而言之，在这个问题上，比 BFS 好得多，实用得多。

于 2010-05-20T08:53:01.610 回答
10

我不知道为什么我的提要中出现了这么老的问题，但是以前的所有答案都是不好的，所以...

DFS 用于在有向图中查找循环，因为它有效。

在 DFS 中，每个顶点都被“访问”，其中访问顶点意味着：

  1. 顶点开始

  2. 访问从该顶点可到达的子图。这包括跟踪从该顶点可到达的所有未跟踪边，并访问所有可到达的未访问顶点。

  3. 顶点完成。

关键特征是在顶点完成之前跟踪从顶点到达的所有边。这是 DFS 的一个特性，但不是 BFS。其实这就是DFS的定义。

由于这个特性，我们知道当一个循环中的第一个顶点开始时：

  1. 没有跟踪循环中的任何边缘。我们知道这一点，因为您只能从循环中的另一个顶点到达它们，而我们正在谈论要开始的第一个顶点。
  2. 从该顶点可到达的所有未跟踪边将在完成之前被跟踪，这包括循环中的所有边，因为它们中没有一条被跟踪。因此，如果有一个循环，我们会在它开始之后，但在它结束之前找到一条回到第一个顶点的边；和
  3. 由于跟踪的所有边都可以从每个开始但未完成的顶点到达，因此找到到这样一个顶点的边总是表示一个循环。

所以，如果有一个环，那么我们保证找到一个开始但未完成的顶点的边（2），如果我们找到这样的边，那么我们保证有一个环（3）。

这就是为什么使用 DFS 在有向图中查找循环的原因。

BFS 不提供此类保证，因此它不起作用。（尽管包含 BFS 或类似子程序的非常好的循环查找算法）

另一方面，无向图只要在任何一对顶点之间有两条路径，即当它不是一棵树时，就有一个循环。这在 BFS 或 DFS 期间很容易检测到——追踪到新顶点的边形成一棵树，任何其他边都表示一个循环。

于 2019-10-03T01:59:12.417 回答
5

BFS 不适用于有向图寻找循环。将 A->B 和 A->C->B 视为图中从 A 到 B 的路径。BFS 会说，在沿着 B 被访问的路径之一走之后。当继续下一条路径时，它会说再次找到标记的节点B，因此，那里有一个循环。显然这里没有循环。

于 2015-01-29T06:00:38.337 回答
2

如果你将一个循环放置在一棵树中的一个随机点上，当它覆盖了大约一半的树时，DFS 将倾向于击中循环，一半的时间它已经遍历循环所在的位置，一半的时间它不会（并且平均会在树的其余一半中找到它），因此它将平均评估树的大约 0.5*0.5 + 0.5*0.75 = 0.625。

如果您将循环放置在树中的随机位置，则 BFS 只有在评估该深度的树层时才会倾向于命中循环。因此，您通常最终不得不评估平衡二叉树的叶子，这通常会导致评估更多的树。特别是，有 3/4 的时间，两个链接中的至少一个出现在树的叶子中，在这些情况下，您必须平均评估树的 3/4（如果有一个链接）或 7/树的 8 个（如果有两个），所以你已经达到了搜索 1/2*3/4 + 1/4*7/8 = (7+12)/32 = 21/32 = 的期望0.656... 的树，甚至没有增加搜索树的成本，并且在远离叶子节点的地方添加了一个循环。

此外，DFS 比 BFS 更容易实现。因此，除非您对周期有所了解（例如，周期可能位于您搜索的根附近，此时 BFS 为您提供了优势），否则它就是您要使用的。

于 2010-05-19T21:53:05.163 回答
1

BFS当您想在有向图中找到包含给定节点的最短循环时，您必须使用它。

例如：在此处输入图像描述

如果给定节点是 2，则存在三个循环，它是 - [2,3,4]，[2,3,4,5,6,7,8,9]&的一部分[2,5,6,7,8,9]。最短的是[2,3,4]

为了使用 BFS 实现这一点，您必须使用适当的数据结构显式维护访问节点的历史记录。

但是对于所有其他目的（例如：寻找任何循环路径或检查循环是否存在），DFS由于其他人提到的原因，这是明确的选择。

于 2020-05-28T10:02:33.677 回答
1

要证明一个图是循环的，你只需要证明它有一个循环（边直接或间接指向自身）。

在 DFS 中，我们一次取一个顶点并检查它是否有循环。一旦找到一个循环，我们就可以省略检查其他顶点。

在 BFS 中，我们需要同时跟踪许多顶点边，并且通常在最后你会发现它是否有循环。随着图大小的增长，与 DFS 相比，BFS 需要更多的空间、计算和时间。

于 2015-07-28T01:32:24.767 回答
0

这有点取决于您是在谈论递归还是迭代实现。

Recursive-DFS 访问每个节点两次。Iterative-BFS 访问每个节点一次。

如果要检测循环，则需要在添加邻接关系之前和之后调查节点——无论是在节点上“开始”还是在节点上“结束”时。

这需要在 Iterative-BFS 中做更多的工作，因此大多数人选择 Recursive-DFS。

请注意，使用 std::stack 的 Iterative-DFS 的简单实现与 Iterative-BFS 具有相同的问题。在这种情况下，您需要将虚拟元素放入堆栈中以跟踪您何时“完成”在节点上的工作。

有关 Iterative-DFS 如何需要额外工作来确定何时“完成”节点的更多详细信息，请参阅此答案（在 TopoSort 的上下文中回答）：

使用没有递归的 DFS 进行拓扑排序

希望这可以解释为什么人们偏爱 Recursive-DFS 来解决您需要确定何时“完成”处理节点的问题。

于 2016-02-09T20:28:46.703 回答
0

我发现BFS和DFS都可以用来检测循环。有些问题提到 BFS 不能与有向图一起使用。我谦虚不同意。

在 BFS-Queue 中，我们可以跟踪父节点列表/集，如果再次遇到相同的节点（直接父节点除外），我们可以将其标记为循环。所以这种方式 BFS 也应该与有向图一起使用。

尽管与 DFS 相比，这将是非常低效的内存，这也是我们主要使用 DFS 的原因。

  1. DFS 内存高效
  2. DFS 更容易可视化，因为它已经使用了显式/隐式堆栈
于 2021-11-21T08:17:07.063 回答