是否存在 BFS 不会终止的情况？ (假设分支因子b是有限的)
最佳答案
只有无限图的 BFS，当搜索没有特定的、可到达的目标时。 (你当然可以有一个无限图和一个有限的分支因子。一个无限高的二叉树就足够了。)
根据其定义，BFS 算法只查看一个顶点一次，并且每次迭代查看一个顶点。因此，具有任意有限个顶点的图的 BFS 必须终止。
如果 BFS 有一个可达的目标 T，则令 P 为从源到目标的路径。如果分支因子最多为 b，则在 P^b 步之后 BFS 必须找到 T。
编辑
回想起来我明白了这个问题的意义所在。如果 BFS 是针对无限大有向图上的特定目标节点 T，那么如果搜索从 T 不可访问的节点开始，BFS 将无法终止，即使分支因子是有限的。例如，假设您有任何无限大的 DAG。那么搜索起始节点的前任节点 T 是不可访问的，因此 BFS 将永远运行而不会找到它。注意，这不会发生在连接的、无向图上。
关于algorithm - 是否存在广度优先搜索不会终止的情况？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25476145/