为什么 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。

最短路径