BFS算法原理和生成树性质证明

1、BFS算法基本思想和证明以及广度优先树最重要的还有实现张季伦本来想直接写证明的，这篇文章的最初主题是证明在无权图下BFS所产生的生成树中由起点（根节点）到任意可达节点的通路（轨道）都是起点到该节点的最短路径。可是后来发现我们的教材实在是对BFS原理和复杂度证明得很少，往往只是写写伪代码然后对复杂度一笔带过，所以干脆这次连同BFS的原理和复杂度一起写出来分享。在这之前，大家至少需要看得懂以C为借鉴所写的伪代码，以及需要对图论的基础知识有一点了解。对于对数据结构有了解的同学来说，很容易知道我们一般用邻接表或者邻接矩阵以及十字矩阵来实现图的数据结构。今天在这里我用邻接矩阵实现。这次也准备放出完整调试

2、后源码给大家参考，语言是C和C+混编的。Part 1.BFS原理分析：首先，广度优先搜索算法的目的是探索一个未知连通结构的图，并把这个图的连通性通过其他数据导出。下面来描述一下BFS算法的基本流程。前期工作：为了使BFS运行工作更加流畅和有条理，我们为算法结构添加如下辅助数据量。1. 向量 COLORELEMETS_NUMBER: 长度为结点个数的向量，用于标明即时结点与已遍历范围的相对位置。2. 父节点向量SUPERELEMENTS_NUMBER:长度同上，数据类型为索引类型，标明某一结点的父节点位置。3. 通路距离向量DISTANCEELEMENTS_NUM:标识在确定的一个BFS运行实例

3、中起点结点到其他结点的距离。4. 辅助队列QUEUE:为了为待遍历的节点提供缓冲。算法开始：这时表示以邻接矩阵表示的图的相关边的数据和起点索引已经传入方法。（令索引为index）第一步：初始化将所有节点的COLOR值置为white。将所有节点的SUPER值置为-1。将所有节点的DISTANCE值置为INF。将COLORindex置为Gray。将SUPERindex置为-1。将DISTANCEindex置为0。执行enQueue（start index）。第二步：循环不变式工作如果队列不为空，则从队列中弹出一个索引元素temp，对它做以下工作：考察与temp索引指向节点的所连通的所有节点，然后对

4、所有有联通的并且颜色不是黑色的节点做以下修改：1. 将所有与temp联通节点的COLOR向量对应值置为Gray。2. 将所有与temp联通节点的SUPER值置为temp。3. 将所有与temp联通节点的DISTANCE对应值设为DISTANCEtemp+1。4. 将所有与temp联通节点的压入队列。最后将temp节点的COLOR值COLORtemp置为black。以上就是BFS的运行流程，下面来解释一下下。BFS的主要思想是它引入了标记变量“颜色COLOR”来标识节点的遍历状态。我们定义，当一个节点没有被BFS算法发现时，它是白色的；当一个节点被发现，而它的子节点没有被发现时，它是灰色的；当一

5、个节点被发现并且它的子节点也被发现了，他就是黑色的。这里的父子节点意思是代表一种发现顺序上的时间关系，如果节点A和B连通，且A先于B被发现，那么我们说A节点是B节点的父节点。简单的说来，黑色节点是出于已遍历范围内部的；灰色节点是出于已遍历和未遍历的节点的分界线；白色节点是在已遍历范围之外的。如图：（其实这个图是有特殊性的，为什么我不用普遍性的图呢？那要等我们证明完以后的问题才知道）我们对黑色节点和灰色节点已经了解了它们的局部结构，而对于位置连通性的白色节点，它们在这一个确定的状态里相当于是游离的。BFS算法要求给出一个起点，从这个起点开始对所有的节点遍历探索；于是，在算法开始时，我们将这个起点

6、压入队列，将他的颜色设为灰色，因为此时他的外围全部都是未被发现的节点。同样，对于父节（前驱）点数组和距离数组（设定相应的值起点没有父节点，起点到起点的距离为一）。接下来，只要队列不为空，就一直从队列中弹出节点元素，并对这个元素做操作；首先，我们考察与这个元素连通且不是黑色的所有节点，然后对这些节点相应的数据做更新。例如：将这些节点的颜色置为灰色，因为在他们被发现后，它们变成了遍历范围的边界；它们到起点的距离被置为弹出元素到起点距离加一；它们的父节点被设定为弹出的这个元素；最后他们都被压入队列；然后我们把当前弹出的这个节点的颜色设置为黑色，因为在与他联通的子节点都被发现后，他就退回到遍历范围内部

7、了。在这里给出伪代码：/*GELEMETS_NUMELEMENTS_NUM;SUPERELEMENTS_NUM;DISTANCEELEMENTS_NUM;COLORELEMENTS_NUM;QUEUE;NODE FLAG WITH INDEX :0 , 1 ,2 . , ELEMENTS_NUM*/VOID BFS(G , SUPER , DISTANCE , COLOR , QUEUE, S)/S MEANS START NODE INDEXCOLORS=GRAY;SUPERS=-1;/-1 MEANS NO SUPER NODEDISTANCES=0;ENQUEUE(S)/SET S NO

8、DE INTO QUEUEWHILE(QUEUE IS NOT EMPTY)NODE TEMP=DEQUEUE();/PIK OUT A NODE FROM QUEUEFOR EACH NODE LNODE LINKING WITH TEMPIF(COLORLNODE=WHITE)COLORLNODE=GRAY;DISTANCELNODE=DISTANCETEMP+1;/FOR UNDIRECTED GRAHSUPERLNODE=TEMP;ENQUEUE(LNODE);COLORTEMP=BLACK;RETURN;算法复杂度分析：关于BFS的时间复杂度，其实用不着用渐进方法去分析，我们可以看到

9、；算法的主要时间开销在唯一的一个while语句上，只要队列不为空，while语句就一直执行；而在while语句内部有一个for each语句，可能大家觉得这个for each 需要分析分析，其实不然，for each只是给出了所有与一个节点相邻的节点，这个东西是线性的。从全局来看，我们会对除了S节点之外的所有节点至多做一次COLOR WHITE操作，至多一次COLOR GRAY操作，至多一次COLOR BLACK操作，加上各自的SUPER和DISTANCE操作，而这些操作都是常数级别的，所以整个算法的时间开销是关于节点个数的线性级别的。源码在这里（原谅我用这么风骚的色调，这个对眼睛很好）：首先

10、是公共变量，常量：然后是indexQueue类的实现（一个专门设计用于存储数组索引的队列）：然后是BFS主方法，以及一个递归的寻路算法（这个和我们一会儿证明的东西有很大关系）以及一个简易的main：Part 2.BFS生成最短路径的完整证明（从最最初条件开始）：BFS算法在完成了之后，假定从起点到某一节点的边数为K，这是又BFS生成的一条通路。有一个事实是，如果我们让起点和终点不变，一定不能找出另一条通路，使这另一条通路的边数小于BFS原来生成的那一条通路。简单地说，BFS生成的任意连通路径在无权图的条件下都是最短的。下面我们要来证明它，这是Dijstra算法的一个思想，而Dijstra算法的

11、目的就是找出两给定节点的最短连通路径。下面我们的证明过程将是形式化以及条件比较严密的：定义：我们定义符号S（）。S（s，v）表示s到v所有可行路径中的最少边数路径。你可以看到，实际上我们讨论的是路径的边数问题，当然，再无权图的情况下，边数和最优权是一回事。子定理1：假设G=（V,E）是一个图，s为G的一个节点（顶点），对于某一条边（u，v）V，存在：S（s，v）<=S（s，u）+1证明：首先我们知道，如果s定点和u不连通，那么S（s，u）为无限大。试想一下，如果s和u是连通的，那么由于（u,v）V，所以s和v也必然是连通的，这个时候命题是成立的（s到v的最短距离不可能比s到u更长）。如果

12、s和u不是联通的，那么不管s和v到连不连通，命题也都是成立的。再来看看我们的证明逻辑，如果我们要想证明BFS的生成路径（DISTANCEv）是最短距离，那么我们就要至少证明S（s，v）和DIATANCEv,或者说S（s，v）<DIATANCEv。我们要让DISTANCEv成为S（s，v）的上界才可以。子定理2：假设G=（V,E）是一图，我们针对某一起点顶点s运行BFS算法，那么在算法运行完成后，对于任意其他节点，BFS所生成的DISTANCEn，都存在：DISTANCEv>=S(s,v)要证明这个式子，需要从缓冲队列这个地方入手，我们要讨论队列在每个状况下这个式子成立与否。1） .

13、初状态：我们来看看起点s被压入队列之后的情况，由于此时其他节点的distance值均为INF（无限大，未被发现），而distances的值为0；所以：DISTANCEs=0>S(s,s)=0DISTANCEV-s=INF>=S(s,v)于是式子成立。2) .普遍状态：假设现在BFS开始了对某一结点u的遍历，发现了与u连通的一个节点v。注意，这时DISTANCEu>=S(s,u)是成立的。于是有：DISTANCEu>=S(s,u).#0DISTANCEv=DISTANCEu+1.#1子定理1中证明了：S（s，v）<=S（s，u）+1.#2当#0,#1和#2合起来时，

14、结果就明了了：DISTANCEu+1=DISTANCEv>=S(s,u)+1>=S(s,v)于是命题仍然成立。在分析复杂度时提到，一个节点至多被压入队列一次，至多被弹出队列一次，所以说普遍状态对于每一个被新发现的节点只会运行一次。于是整个命题就得证了。子定理3:这一个关于各个节点入队列顺序的证明。命题：如果QUEUE是G=(V,E)运行BFS算法时所运用的辅助队列，在QUEUE中包含顶点v1,v2,v3,.,vr，v1为队列头，vr为队列尾；那么存在：DISTANCEvr<=DISTANCEv1+1且DISTANCEvi<=DISTANCEv（i+1）i=1,2,3,4

15、,.,r-1注意：i，r，i+1均为下标证明：我们还是按照队列的状态来证明命题：1) .初始状态：当队列里只有一个节点s时，可以知道v1与vr相等，那么命题自然成立。2) .普遍状态：a) 普遍状态意味着在此时我们已经承认命题在初始状态时成立。b) 其实普遍状态的证明就是证明队列元素在发生改变之后命题仍然成立。i. 对队列添加一个元素，命题成立。ii. 对队列删除一个元素，命题成立。假设现在BFS算法在遍历一个节点v时，出现了以下需要添加节点的情况：第一种情况是我们在遍历v时第一次发现一个新节点（白色）。于是我们把它添加进队列。所以这时有：DISTANCEv+1=DISTANCEv（i+1）所

16、以：DISTANCEvi<=DISTANCEv（i+1）成立。第二种情况是我们在对灰色v遍历了一段时间后，发现了白色联通节点v1，之后接着又同是发现了另一个白色节点v2，于是可以知道v1，v2都是与v连通的节点。由于既然v1，v2在遍历v的联通节点时被找到，所以他们的DISTANCE值只会在此处被修改，且有：DISTANCEv+1=DISTANCEv1+DISTANCEv2于是第二种情况仍然成立。假设在BFS主循环不变式（队列不为空便执行的命令块）开始时，队列弹出了一个元素节点v1然后我们证明剩余的队列中元素仍然满足这个命题：重新考察这个弹出了节点的队列，其头节点为v2，我们现在要分析v

17、2和原先v1的关系，由于v2是后于v1添加的，所以它满足：DISTANCEv2<=DISTANCEv1+1DISTANCEv1<=DISTANCEv2如果说v1不是我们最初算法的起始节点s，那么要么v1和v2的距离要么相等要么v2的距离比v1大一。当v1是初始节点s时，v2距离绝对比v1大1。、由于：DISTANCEvr<=DISTANCEv1+1DISTANCEv2=DISTANCEv1或者DISTANCEv2=DISTANCEv1+1所以：DISTANCEv2+1>=DISTANCEv1+1>=DISTANCEvr即：DISTANCEv2+1>=DIST

18、ANCEvr而对于证明：DISTANCEvi<=DISTANCEv（i+1）i=1,2,3,4,.,r-1由于对头元素的弹出不影响上式，所以它仍然成立。于是，整个命题就成立了。子定理4（最后一个子定理）：如果在BFS运行过程中，将vi和vj插入队列，且vi先于vj插入，那么DISTANCEvi<=DISTANCEvj证明：结合BFS算法的特征，我们知道要么vi和vj的链接节点是同一个节点，要么vi是vj的链接节点（通过对vi遍历找到白色的vj），所以说DISTANCEvi=DISTANCEvj或者DISTANCEvi+1=DISTANCEvj。命题成立。同样也可用子定理3来证明这个

19、东西。最后的结论证明，证明广度优先搜索的正确性：广度优先搜索的正确性是这样描述的，对于一个无权图G（V,E），对于一个起始节点s运行BFS算法，在算法运行完成之后对于每一个属于V而不是s的节点v，都存在：DISTANCEv=S(s,v)并且任意一个从s开始除了s之外的可达节点v都存在s到v的最短路径一定是s到PARENTv的最短路径加上(PARENTv，v)。证明：我们在前面已经证明了DISTANCEv>=S(s,v)，现在我们要严格证明等号成立。在Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest、Clifford Stein的Int

20、roduction to Algorithms Second Edition中在这个地方是运用反证法引出了一个矛盾来证明命题的，但是我个人觉得不利于大家理解，不会用反证法，我将从我们以前的所证明的子定理来证明这个命题。我将用归纳法证明，而归纳的条件就是各个节点进入队列的时机和所处位置。首先，我们需要再来确认一下对S标记的定义。S（s，v）表示从s到v所经历的最短边数（前提是s到v是可达的）。所以，有一点是可以明确的，如果说我们要在一个图中手动找到一条S（s，v）路径的话，那将是一连串的截弯取直工作，如果说在S（s，v）中，存在两条边（vi，v（i+1），（v（i+1），v(i+2)），而又存在

21、vi和v（i+2）连通，那么（vi，v（i+1），（v（i+1），v(i+2)）实际在S（s，v）中是无效的，所以说（vi，v(i+2)）将替代（vi，v（i+1），（v（i+1），v(i+2)）。现在，我将一个BFS具体实例和它说操作的图的各个节点分类。节点将被“分层”。具体定义如下：1.同层节点：在同一个循环不变式循环过程中发现的节点，对于任意两个是同层节点的节点的v1，v2存在：PARENTv1=PARENTv2，起点s不存在和它同层的节点，s所在的层只有s一个元素。同层节点在QUEUE中都是相邻的。2. 邻层节点：如果DISTANCEv1=DISTANCEv2+1的话，那么v1，v2是邻层节点。邻层节点之间的QUEUE位置关系为：如果v1和v2为邻层节点，v1先于v2入队列，那么：v1和v2相邻 或者：对于任意一个存在于队列中且位置在v1和v2之间的节点vi，那么存在：v2>=DISTANCEvi>=v1 且：当v2>DISTANCEvi成立时，v2=DISTANCEvi+1必然成立。当v1<DISTANCEvi成立时，v1=DISTANCEvi-1必然成立。3. 头层节点：s节点。4. 尾层节点：对于整个