有没有可能出现广度优先搜索不会终止的情况？

Question

是否存在 BFS 不会终止的情况？（假设分支因子 b 是有限的）

Answer 1

只有无限图的 BFS 并且当搜索没有特定的、可到达的目标时。（你当然可以有一个具有有限分支因子的无限图。无限高的二叉树就足够了。）

BFS 算法根据其定义只查看一个顶点一次，并且每次迭代查看一个顶点。因此，具有任意有限数量顶点的图的 BFS 必须终止。

如果 BFS 有一个可达目标 T，那么让 P 是一条从源到目标的路径。如果分支因子至多是 b，那么在 P^b 步之后，BFS 必须找到 T。

编辑

我想回想起来，我看到了这个问题的意义。如果 BFS 是针对无限大有向图上的特定目标节点 T ，那么如果搜索从 T 不可访问的节点开始，即使分支因子有限，BFS 也将无法终止。例如，假设您有任何无限大的 DAG。那么作为搜索开始节点的前驱节点的任何节点 T 都是不可访问的，因此 BFS 将永远运行而不找到它。注意，这不会发生在连接的无向图上。