广度优先搜索查询

Question

我正在尝试解决一个问题，以找到从源（UBC）到目标（DT）的路径。

问题的结果是UBC-> PT-> KT-> DT。我们如何使用BFS获得此结果？

Answer 1

广度优先搜索仅计算边缘，不计算边缘成本。 （等效地，它将所有边视为成本为1。）

因此，您将UBC放入队列，然后它将向外扩展：

深度1：PT，SL

深度2：KT，SG，KD，MP

深度3：DT，AP

请注意，一旦从KT生成DT，BFS就可以终止，因为在那一点上已经知道不可能有更短的DT路径。