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

Question

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

Answer 1

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

root -> v1 -> v2 -> v3 -> ... 永远持续下去
|-> 你。

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