首先证明BFS中的队列具有的两个性质

• 两段性(队列中同时存的所有点到起点的距离之间的差值最多是$1$，即$q[x,…,x,x+1,…,x+1]$，最多有两段)
• 单调性(队列中存在的元素到起点的距离一定是单调递增的，如果存在两段则一定是前面一段是$x$，后面一段是$x+1$)

证明单调性和两段性(数学归纳法)

1. 证明初始状态具有单调性和两段性：初始状态队列中只有一个元素，这个元素到起点的元素是$0$，所以队列是满足单调性和两段性的

2. 证明队列中间的某个状态具有单调性和两段性：假设队列中间某个状态满足单调性和两段性，当我们从队头取出来一个和起点距离为$x$的点，然后我们会把这个$x$所能扩展到的点全部加到队尾去，由于这些扩展的所有的边的距离都是$1$(如果扩展的点已经被遍历过了就不管它)，所以其实就是往队尾添加了若干个与起点距离为$x+1$，因此可以发现当我们从队头取出一个与起点距离为$x$的点，然后把这个点所有能扩展到的点全部放到队尾去之后，整个队列仍然具有单调性和两段性

有了这个性质之后，我们可以类比一下堆优化版的Dijkstra算法

堆优化版的Dijkstra算法：最开始先把起点入队，然后当队列不空的时候，每次取出优先队列的队头，接下来循环一边取出来的点所有能到的边，然后更新。

我们可以发现：$BFS$里面的队列永远都具有单调性和两段性，因此每次我们取队头的时候，就相当于是取了当前队列里面的一个最小值，所以说如果所有的边权为$1$的话，那么在$BFS$里面的队列就相当于是堆优化版的$Dijkstra$算法里面的优先队列，因为$Dijkstra$算法是正确的，所以$BFS$算法也是正确的

这里再试着不借助Dijkstra算法来证明一下

$BFS$算法和$Dijkstra$算法还是有一些区别的，$Dijkstra$算法是说当我们第一次从优先队列里面出队的时候，它就是最小值，入队不一定是最小值，但是在$BFS$算法里面，可以把时间再往前推一些，它从入队开始就是最小值了，因为所有点只会入队一次，一旦入队了值就不会被改变，所以可以把时间推到入队的时候

证明入队的时候它就已经是最小值：(数学归纳法+反证法)

归纳假设所有已经出队的元素，它的最小值已经确定了永远不会被改变了

首先最初的时候，一个元素都没有出队，所以假设是成立的

然后从队头取出$x$元素之后，(反证法)假设$x$当前的距离不是最小值，也就是说$x$会被当前队列当中的后面的某一个点经过某一条路径回到$x$来更新，并且更新之后$x$的距离会严格变小，由于在$x$前面已经出队的元素的最小值已经确定了，那么它们能更新的点已经更新完了，所以说，从后面的某一个点出发经过某一条路径回到$x$的这个路径是一定不会经过已经出队的点的，也就是说这个路径上的所有的点，要么是在当前的队列后面，要么是还没有入队的点。

分析到这里，我们来看一下有什么矛盾的，首先队列是具有单调性的，也就是说后面的点的距离是大于等于当前$x$的距离的，并且每条边的权重都是$1$，所以说后面的点经过某一条路径回到$x$来更新时，这条路径求出来的$x$的距离一定是大于当前$x$的最小距离的，所以实际上是没法更新的，那么就矛盾了，因此我们当前从队头取出的元素，它的当前距离就已经是最小值了

经过证明，得出所有元素在出队的时候就已经是最小值了，由于$BFS$每个点只会入队一次，每个点一旦入队它的值就不会改变了，所以在每个点入队的时候，它与起点的距离就已经是最小值了，到此我们就在不借助$Dijkstra$算法的前提下求出了$BFS$算法求所有边权都是$1$的单源最短路的方法的正确性