java - 如果它在 BFS 图中而不是 DFS 图中，为什么你保证能找到你的结果？

Question

我在某处读到 DFS 不适合找到解决方案，而 BFS 是..为什么？我真的不明白这是怎么回事..有人可以为我证明一个案例来证明这一点吗？

Answer 1

DFS，因为它是深度优先搜索，可能会卡在无限分支中，永远无法到达您正在寻找的顶点。BFS 每次迭代都会遍历与根相同距离的所有顶点，无论它们在哪个分支上，因此它最终会找到所需的顶点。
例子：

root -> v1 -> v2 -> v3 -> ... 永远存在
|-> u.

在此示例中，如果 DFS 从根目录开始，然后继续到 v1。它永远不会到达你，因为它进入的分支是无限的。BFS 将从 root 到 v1 或 u，然后到另一个。

Answer 2

DFS 和 BFS 的输出（在具有有限数量顶点的图上）终止并产生一条路径（或者更确切地说是一棵树，但 OP 似乎只对该树的一条路径感兴趣）。图中是否存在循环并不重要，因为两个过程都会记录已访问过哪些顶点，从而避免多次访问同一个顶点。DFS/BFS 的任何合理实现都可以做到这一点 - 否则您将仅限于非循环图（请参阅 CLRS 中给出的伪代码）。

正如@yurib 提到的，如果图有无限数量的节点，则 dfs 可能会永远持续下去。由于存在无限节点，我们实际上无法跟踪已访问过哪些顶点（这可能会占用无限内存），即使我们这样做了，也可能存在一条包含唯一顶点的无限路径，而该路径不包含我们正在寻找的顶点.

然而，这并不是 DFS 并不总能找到最短路径的唯一原因。即使在有限图中，DFS 也可能无法找到最短路径。

主要原因是 BFS 在移动到距离 x+1 的节点之前，总是先探索距离根节点 x 处的所有节点。因此，如果在距离 k 处找到一个节点，我们可以确定从根到该节点的最小距离是 k 而不是 k-1、k-2、...、0（否则我们会更早遇到它）。

另一方面，DFS 基本上沿一条路径探索节点，直到该路径上没有更多新节点，然后再查看另一条路径。DFS 只是以本质上任意的顺序逐个探索节点的每个后继节点。这意味着它可能会找到一条到目标节点的更长路径，因为它只是碰巧先探索了该路径。

在上图中，BFS 将首先探索 B 和 E，然后通过 E 到达 D - 为我们提供到 D 的路径，即 root->E->D。DFS 可能会先从 B 开始搜索，从而找到路径 root->B->C->D，这显然不是最短的。

请注意，关键决定是在 E 之前探索 B。DFS 很可能已经选择了 E 并得出了正确的答案。但是通常没有办法知道首先走哪条路径（如果我们知道无论如何我们都会知道最短路径）。对于 DFS，它找到的路径仅取决于它探索后继节点的顺序，这可能会或可能不会产生最短路径。

Answer 3

@yurib 是正确的，但还有一个更复杂的问题。

如果所需的顶点不在图中，那么如果存在循环，则 BFS 或 DFS 都不会终止……除非您采取措施检测循环。如果您正在采取措施检测周期，BFS 和 DFS 都将终止。