为什么广度优先遍历得到的是最短路径

假设我们需要找到从A到G的最短路径：

在BFS中使用队列这种数据结构，那么我们来模拟一遍找到最短路径的这样的过程

1、A入队，队列状态：A 到A的距离为0

2、队列不为空，A出队，找到A相邻的节点 BCD然后加入到队列中，队列状态：B C D ，它们到A的距离为父节点A的距离加一，所以距离为1。

3、队列不为空，B出队（因为是先进先出，这里不管是B、C还是D先进队列，都不影响最短路径的计算，因为最短路径的计算是按照父节点的距离+1计算的，而不是出队的次数等等啥计算的。但是是会影响搜索路径的，因为在搜索中节点如果先走B肯定会后搜索到G，但是先走D肯定会先搜索到G）找到B的相邻节点然后入队，队列状态：C D E F ，EF到A的距离为父节点B的距离加一，为2.

4、队列不为空，C出队，C没有相邻节点，队列状态：D E F

5、队列不为空，D出队，添加D相邻节点，队列状态：E F H I J，HIJ到A的距离为父节点的距离加一，为2

6、队列不为空，E出队，E没有相邻节点，队列状态：F H I J

7、队列不为空，F出队，F没有相邻节点，队列状态：H I J

8、队列不为空，H出队，添加H的相邻节点，队列状态：I J K，K到A的距离为H的距离加一，为3

9、队列不为空，I出队，添加I的相邻节点，队列状态：J K G L,G和L到A的距离为I的距离加一，为3

10、队列不为空，J出队，J没有相邻节点，队列状态：K G L

11、队列不为空，K出队，K没有相邻节点，队列状态：G L

12、队列不为空，G出队，G刚好是需要找的节点，所以最短路径就是G到A的距离为3

所以广度优先遍历找到的绝对是最短的路径，因为它每次都是从最短的距离上加一。且与遍历的相邻节点的顺序无关。