如果使用BFS而不是DFS在图形中，为什么可以保证找到结果？

Question

我读过某处的文章，但DFS却没有保证DFS可以找到解决方案，为什么？我真的不知道这是怎么回事..有人可以为我演示一个证明这一点的案例吗？

Answer 1

由于DFS进行了深度优先搜索，因此它可能会卡在无限分支中，并且永远不会到达您要查找的顶点。BFS每次迭代都会遍历所有与根相同距离的顶点，而不管它们位于哪个分支上，因此它将最终找到所需的顶点。
例：

根-> v1-> v2-> v3-> ...永远持续下去
|-> u。

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