为什么为什么 BFS 可以搜索到最短路径 可以搜索到最短路径 估计很多初学者对这个问题一直不明白，为什么使用 BFS 进行广度搜索，一定可以搜索到最短路径。 讲真，在学校里学习 BFS 的时候，自己也没完全明白为什么。老师这么教，课本这么写，我就这么记。 其实回答这个问题很简单，请大家仔细观察下图，也就是使用 BFS 完成对树的搜索。比如，我要搜索节点 A 到节点 G 的最短 路径。如下动图所示： 在 BFS 中，我们使用了数据结构中的一个队列（queue），我们知道队列的特性是 FIFO（First In First Out），也就是先进先 出。正是这个 FIFO 特性，保证了我们第一个到达目标节点一定是最短路径。下面解释一下整个 BFS 的过程，我们整个搜索 的过程是这样的： 1、将开始节点 A 的距离设置为 0，并将节点 A 加入到队列 q 中。此时队列只有一个结点 A。 2、队列 q 不为空，我们弹出队列的首节点，也就是 A，找到 A 的所有邻接节点。从上图可以看出，也就是 B、C、D，我们 将 B、C、D 的距离设置为 1（即父节点 A 的距离加一），然后将 B、C、D 加入到队列中。这样队列内的元素就是 B,C,D。 注意先加谁是会影响距离的，只影响那些节点搜索路径。具体可以自己思考一下，如果我们先加入 D，然后再加入 C，再加入 B，这样的搜索路径是什么。 3、队列 q 不为空，我们弹出队列的首节点，也就是 B，找到 B 的所有邻接节点。从上图可以看出，也就是 E、F，我们将 E、F 的距离设置为 2（即父节点 B 的距离加一），然后将 E、F 加入到队列中。这样队列内的元素就是 C,D,E,F。 4、队列 q 不为空，我们弹出队列的首节点，也就是 C，找到 C 的所有邻接节点。从上图可以看出，C 没有邻接节点。这样队 列内的元素就是 D,E,F。 5、队列 q 不为空，我们弹出队列的首节点，也就是 D，找到 D 的所有邻接节点。从上图可以看出，也就是 H、I、J，我们将 H、I、J 的距离设置为 2（即父节点 D 的距离加一），然后将 H、I、J 加入到队列中。这样队列内的元素就是 E,F,H,I,J。 6、队列 q 不为空，我们弹出队列的首节点，也就是 E，找到 E 的所有邻接节点。从上图可以看出，C 没有邻接节点。这样队 列内的元素就是 F,H,I,J。 7、队列 q 不为空，我们弹出队列的首节点，也就是 F，找到 F 的所有邻接节点。从上图可以看出，F 没有邻接节点。这样队 列内的元素就是 H,I,J。 8、队列 q 不为空，我们弹出队列的首节点，也就是 H，找到 H 的所有邻接节点。从上图可以看出，也就是 K，我们将 K 的距 离设置为 3（即父节点 H 的距离加一），然后将它们加入到队列中。这样队列内的元素就是 I,J,K。 9、队列 q 不为空，我们弹出队列的首节点，也就是 I，找到 I 的所有邻接节点。从上图可以看出，也就是 G、L，我们将 G、 L 的距离设置为 3（即父节点 I 的距离加一），然后将它们加入到队列中。这样队列内的元素就是 I,J,K,G,L。 10、队列 q 不为空，我们弹出队列的首节点，也就是 I，找到 I 的所有邻接节点。从上图可以看出，I 没有邻接节点。这样队 列内的元素就是 J,K,G,L。 

11、队列 q 不为空，我们弹出队列的首节点，也就是 J，找到 J 的所有邻接节点。从上图可以看出，J 没有邻接节点。这样队 列内的元素就是 K,G,L。 12、队列 q 不为空，我们弹出队列的首节点，也就是 K，找到 K 的所有邻接节点。从上图可以看出，K 没有邻接节点。这样 队列内的元素就是 G,L。 13、队列 q 不为空，我们弹出队列的首节点，也就是 G。G 就是我们要搜索的终点，这样我们知道节点 G 到节点 A 的距离为 3（参考第 9 步）。 这样通过 BFS，我们搜索的 A 到 G 的距离为 3，肉眼观察，我们发现最短路径为 A ->D -> I -> G，也就是最短距离为 3。 作者：努力的老周