《BFS算法原理和生成树性质证明.docx》由会员分享，可在线阅读，更多相关《BFS算法原理和生成树性质证明.docx（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、BFS算法基本思想和证明以及广度优先树最重要的还有实现张季伦本来想直接写证明的，这篇文章的最初主题是证明在无权图下BFS所产生的生成树中 由起点（根节点）到任意可达节点的通路（轨道）都是起点到该节点的最短路径。可是后来 发现我们的教材实在是对BFS原理和复杂度证明得很少，往往只是写写伪代码然后对复杂 度一笔带过，所以干脆这次连同BFS的原理和复杂度一起写出来分享。在这之前，大家至少需要看得懂以C为借鉴所写的伪代码，以及需要对图论的基础知 识有一点了解。对于对数据结构有了解的同学来说，很容易知道我们普通用邻接表或者邻接矩阵以及十 字矩阵来实现图的数据结构。今天在这里我用邻接矩阵实现。这次也准备放
2、出完整调试后源码给大家参考，语言是C和C+混编的。Partl.BFS原理分析：首先，广度优先搜索算法的目的是探索一个未知连通结构的图，并把这个图的连通性通 过其他数据导出。下面来描述一下BFS算法的基本流程。前期工作：为了使BFS运行工作更加流畅和有条理，我们为算法结构添加如下辅助数据量。1 .向量 COLORELEMETS_NUMBER:长度为结点个数的向量，用于标明即时结点与已遍历范围的相对位置。2 .父节点向量 SUPERELEMENTS_NUMBER:长度同上，数据类型为索引类型，标明某一结点的父节点位置。3,通路距离向量 DISTANCEELEMENTS_NUM:标识在确定的一个BF
3、S运行实例中起点结点到其他结点的距离。4 .辅助队列QUEUE:为了为待遍历的节点提供缓冲。算法开始：这时表示以邻接矩阵表示的图的相关边的数据和起点索引已经传入方法。（令索引为 index）第一步：初始化将所有节点的COLOR值置为wMte。将所有节点的SUPER值置为-1。将所有节点的DISTANCE值置为INFo将 COLORindex置为 Gray。将 SUPERindex置为。将 DISTANCEindex置为 0。的子定理来证明这个命题。我将用归纳法证明，而归纳的条件就是各个节点进入队列的时机和所处位置。首先，我们需要再来确认一下对S标记的定义。S (s, v)表示从s到V所经历的最
4、短边数(前提是s到V是可达的)。所以，有一点是可以明确的，如果说我们要在一个图中手动找到一条S (s, v)路径的 话，那将是二连串的截弯取直工作，如果说在S (s , v)中，存在两条边(vi, v (i+1), (v (i+1), v(i+2),而又存在 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 .同层节点：在同
5、一个循环不变式循环过程中发现的节点，对于任意两个是同层节点的 节点的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 且：当 v2DISTANCEvi成立时，v2=DISTANCEvi
6、+1 必然成立。当 v1vDISTANCEvi成立时，v1=DISTANCEvi卜 1 必然成立。3 .头层节点：s节点。4 .尾层节点：对于整个算法最后添加进队列的元素vr,如果某一其他元素vi满足 DISTANCEvi=DISTANCEvr,那末vi节点也是尾层节点，所有尾层节点组成“尾层”。命题中所涉及的节点是除了头层节点之外的所有节点。A),对于头层节点的任意邻层节点v,显然成立，因为S (s , v) =DISTANCEv=1 oB) .对于与A中v节点相邻的，但不是s的节点vk,我们知道：DISTANCEvk=DISTANCEv+1 =2由于子定理1中提到：DISTANCEv=S(
7、s,v)所以有：S(s, vk)S(s,vr),那意味着存在除了 (vr, vl)以外的一条通路连通vr和vl,但是这 条通路的边数大于2,我们的最短边数是不可能舍弃一条边儿选择两条边的(因为截弯取 直)。所以对于尾层节点原命题仍旧成立。所以广度优先搜索的正确性是成立的。Part 3.BFS广度优先树:BFS算法生成为了一棵以s为根节点的广度优先树，因为BFS对图遍历时是选择性的遍 历某些边。而这种遍历又是相当于层序的。所以它生成为了一棵广度优先树。对于广度优先树还可以写一个回溯算法来通过生成的PARENT数组找到任意非s节点 的最短路径。算法在这里就不提了，只是贴出源代码。B2*B31341
8、350136137 ei381391401411 getPath(mt s, int end, mt parent) if(ends)couts ;se if(parentend- )cout*NO pathMendl;getPath(s,parentend,parent); coutendM n:执行 enQueue (start index) o第二步：循环不变式工作如果队列不为空，则从队列中弹出一个索引元素temp,对它做以下工作：考察与temp索引指向节点的所连通的所有节点，然后对所有有联通的并且颜色不是黑 色的节点做以下修改：1 .将所有与temp联通节点的COLOR向量对应值置为G
9、ray。2 .将所有与temp联通节点的SUPER值置为temp。3,将所有与temp联通节点的DISTANCE对应值设为DISTANCEtemp+1。4,将所有与temp联通节点的压入队列。最后将temp节点的COLOR值COLORtemp置为blacko以上就是BFS的运行流程，下面来解释一下下。BFS的主要思想是它引入了标记变量“颜色COLOR来标识节点的遍历状态。我们定 义，当一个节点没有被BFS算法发现时，它是白色的；当一个节点被发现，而它的子节点 没有被发现时，它是灰色的；当一个节点被发现并且它的子节点也被发现了，他就是黑色的。这里的父子节点意思是代表一种发现顺序上的时间关系，如果
10、节点A和B连通，且A 先于B被发现，那末我们说A节点是B节点的父节点。简单的说来，黑色节点是出于已遍历范围内部的；灰色节点是出于已遍历和未遍历的节 点的分界线；白色节点是在已遍历范围之外的。如图：(其实这个图是有特殊性的，为什么我不用普遍性的图呢？那要等我们证明完以后的问 题才知道)我们对黑色节点和灰色节点已经了解了它们的局部结构，而对于位置连通性的白色节点，它们在这一个确定的状态里相当于是游离的。BFS算法要求给出一个起点，从这个起点开始对所有的节点遍历探索；于是，在算法开 始时，我们将这个起点压入队列，将他的颜色设为灰色，因为此时他的外围全部都是未被发 现的节点。同样，对于父节(前驱)点数
11、组和距离数组(设定相应的值起点没有父节点，起 点到起点的距离为一)O接下来，只要队列不为空，就向来从队列中弹出节点元素，并对这个元素做操作；首先， 我们考察与这个元素连通且不是黑色的所有节点，然后对这些节点相应的数据做更新。例如： 将这些节点的颜色置为灰色，因为在他们被发现后，它们变成为了遍历范围的边界；它们到 起点的距离被置为弹出元素到起点距离加一；它们的父节点被设定为弹出的这个元素；最 后他们都被压入队列；然后我们把当前弹出的这个节点的颜色设置为黑色，因为在与他联 通的子节点都被发现后，他就退回到遍历范围内部了。在这里给出伪代码：/*GELEMETS_NUMELEMENTS_NUM;SUP
12、ERELEMENTS_NUM;DISTANCEELEMENTS_NUM;COLORELEMENTS_NUM;QUEUE;NODE FLAG WITH INDEX :0,1 ,2 .，ELEMENTS_NUM*/VOID BFS(G, SUPER, DISTANCED , COLOR, QUEUE, S)/SMEANS START NODE INDEXCOLORS=GRAY;SUPERS=-1 ;/-1 MEANS NO SUPER NODEDISTANCES=O;ENQUEUE(S)/SET S NODE INTO QUEUEWHILE(QUEUE IS NOT EMPTY)NODE TEMP
13、=DEQUEUE();/PIK OUT A NODE FROM QUEUEFOR EACH NODE LNODE LINKING WITH TEMPIF(COLORLNODE=WHITE)COLORLNODE-GRAY;DISTANCELNODE=DISTANCETEMP+1;/FOR UNDIRECTED GRAH SUPERLNODE=TEMP;ENQUEUE(LNODE);)COLORTEMP=BLACK;RETURN;算法复杂度分析：关于BFS的时间复杂度，其实用不着用渐进方法去分析，我们可以看到；算法的主要 时间开消在惟一的一个while语句上，只要队列不为空，while语句就向来执
14、行；而在while 语句内部有一个for each语句，可能大家觉得这个for each需要分析分析，其实不然，foreach 只是给出了所有与一个节点相邻的节点，这个东西是线性的。从全局来看，我们会对除了 S节点之外的所有节点至多做一次COLOR WHITE操作， 至多一次COLOR GRAY操作，至多一次COLOR BLACK操作，加之各自的SUPER和 DISTANCE操作，而这些操作都是常数级别的，所以整个算法的时间开消是关于节点个数 的线性级别的。源码在这里（原谅我用这么风骚的色调，这个对眼睛很好）: 首先是公共变量，常量：coder : ZhongJilun date : 2013
15、 1 29 vert ion 1.0(debuged)int INF=0010const int MAX= ;0011im AdijMAXMAX;0?12int ParentMAX;0013DistanceMAX;char ColorMAX;&15int start;include /include using n(Tiespac std;/means nopath within two point max arcLenath然后是indexQueue类的实现（一个专门设计用于存储数组索引的队列）:indexQueuefCloss by indxx nr queue;/Queue array
16、mt box /yax length int ror/ending eleer nt bead;/heading elee ：nr w/runtime indextndexQueue( ir t )；cons txx I sEptX) /juge is tHxl enQueue(mt index);mt deQueue();i ndexQueue: ndexQueue(.) ，U(- ) L-；else J;queuef mt L;for。. ) queue。 heock ;rear-; ten-;mx-L;indexQueue: enQueue( nt tndex) r(len-ax) re
17、turn talse;i*(index* ) return alse;i (rejr-len- )rear-;queuerear.index;eUe(rear1;queuerear-index;)len;t ndexQueue: dQueu* ) if(isEpty() return int index;i f(beo(Slen- ) tndexqueuehead;beod-;Rlse(index-queuehead; bead1;)len-;index;然后是BFS主方法，以及一个递归的寻路算法（这个和我们一会儿证明的东西有很大 关系）以及一个简易的main：bool040W50099iee
18、191M2ei03 01040105 eioeM7 einBFS(parameter(s) List int adijMAXMAX, int di stance口， int parent, char color, mt arcnum.int s )/Cheaking parameter(s).if(s ) return false;H(arcnufn ) return false;if(Qdij-NULL) return false;(distance-NULL 11 parent-NULL I I color-NULL) return false;/Intilizing ar rales &
19、 var.mt i-;tnt temp-;indexQueue q=indexQueue(MAX);for(i= ;iarcnum;i-+) distancei=INF;for(i- ;iarcnum;i-M-) parenti=-;for(i-colori-*wT;eueu.191120113eii4115116117ilf119eizi ei22123124125U71281290130 )01310132 void133 eiMini)e0137ei39 ei4e141 )/Get ready primavel state.distances-;parents;color;if(lq.e
20、nQueue(s) return false;/Loopping begins.while(lq.isEmpty()i f(te叩q. deQueue。): 1) return false;temp-q.deQueue();for(i- ;iQrcnum;i*)colori-,g,;parenti=temp;distancei=distancetemp+ ;if(!q.enQueue(i) return false;)colortemp-*b*;return true;getPath(int s,int end,int parent) tf(end-s)coutsMels* H (parent
21、end )coutMNO pathMendl;elsegetPath(s,parentend,parent);coutendn M;)142eio0144145014701480149ei5e151152153154.155int main()int m - , , , ,INF, , ,INF, ,INF,，INF,INF,INF, , , )；int fori,J；(i- ；i ；i+) foj；j ；jr)Part 2,BFS生成最短路径的完整证明(从最最初条件开始)：BFS算法在完成为了之后，假定从起点到某一节点的边数为K,这是又BFS生成的一 条 通路。有一个事实是，如果我们让起点和
22、终点不变，一定不能找出另一条通路，使这另 一条通路的边数小于BFS原来生成的那一条通路。简单地说，BFS生成的任意连通路径在无权图的条件下都是最短的。下面我们要来证明它，这是Dijstra算法的一个思想，而Dijstra算法的目的就是找出两 给定节点的最短连通路径。下面我们的证明过程将是形式化以及条件比较严密的：定义：我们定义符号S Oo S ( s, v)表示s到v所有可行路径中的至少边数路径。你可以看到，实际上我们讨论的是路径的边数问题，固然，再无权图的情况下，边数和 最优权是一回事。子定理1：假设G= (V,E)是一个图，s为G的一个节点(顶点)，对于某一条边(u, v) eV,存在：S
23、 (s, v) =S (s, u) +1证明：首先我们知道，如果s定点和u不连通，那末S ( s, u)为无限大。试想一下，如果s和u是连通的，那末由于(u,v) eV,所以s和v也必然是连通的， 这个时候命题是成立的(s至W的最短距离不可能比s到u更长)。如果s和u不是联通的，那末不管s和v到连不连通，命题也都是成立的。再来看看我们的证明逻辑，如果我们要想证明BFS的生成路径(DISTANCE)是最 短距离，那末我们就要至少证明S ( s, v)和DIATANCEv,或者说S ( s, v) =S(s,v)要证明这个式子，需要从缓冲队列这个地方入手，我们要讨论队列在每一个状况下这个式子 成立
24、与否。1),初状态：我们来看看起点s被压入队列之后的情况，由于此时其他节点的distance值均为INF(无限大,未被发现)，而distanced的值为0；所以：DISTANCEs=0S(s5s)=0DISTANCEV-s=INF=S(s,v)于是式子成立。2) .普遍状态：假设现在BFS开始了对某一结点u的遍历，发现了与u连通的一个节点V。注意,这时 DISTANCEu=S(s,u)是成立的。于是有：DISTANCEu=S(s5u)#0DISTANCEv=DISTANCEu+1#1子定理1中证明了：S (s, v) =S(s5u)+1 =S(s,v)于是命题仍然成立。在分析复杂度时提到，一个
25、节点至多被压入队列一次，至多被弹出队列一次，所以说普 遍状态对于每一个被新发现的节点只会运行一次。于是整个命题就得证了。子定理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,r-1)注意：i, r, i+1均为下标证明：我们还是按照队列的状态来证明命题：1) .初始状态：当队列里惟独一个节点s时，可以知道v1与vr相等，那末
26、命题自然成立。2) .普遍状态：a)普遍状态意味着在此时我们已经承认命题在初始状态时成立。b)其实普遍状态的证明就是证明队列元素在发生改变之后命题仍然成立。i . 对队列添加一个元素，命题成立。ii .对队列删除一个元素，命题成立。假设现在BFS算法在遍历一个节点v时，浮现了以下需要添加节点的情况：第一种情况是我们在遍历v时第一次发现一个新节点(白色)。于是我们把它添加 进队列。所以这时有：DISTANCEv+1 =DISTANCEv (i+1)所以：DISTANCEvi=DISTANCEv (i+1)成立。第二种情况是我们在对灰色v遍历了一段时间后，发现了白色联通节点v1 ,之后 接着又同是
27、发现了另一个白色节点v2,于是可以知道v1 , v2都是与v连通的节点。由 于既然v1, v2在遍历v的联通节点时被找到，所以他们的DISTANCE值只会在此处被 修改，且有：DISTANCEv+1 =DISTANCEv1 +DISTANCEv2于是第二种情况仍然成立。假设在BFS主循环不变式(队列不为空便执行的命令块)开始时，队列弹出了一 个元素节点v1然后我们证明剩余的队列中元素仍然满足这个命题：重新考察这个弹出了节点的队列，其头节点为v2,我们现在要分析v2和原先v1 的关系，由于v2是后于v1添加的，所以它满足：DISTANCEv2=DISTANCEv1 +1DISTANCEv1 =D
28、ISTANCEv2如果说v1不是我们最初算法的起始节点s,那末要末v1和v2的距离要末相等要末v2 的距离比v1大一。当v1是初始节点s时，v2距离绝对照v1大1。、由于：DISTANCEvr=DISTANCEv1 +1 =DISTANCEvr即：DISTANCEv2+1 =DISTANCEvr而对于证明：DISTANCEvi=DISTANCEv (i+1)i=1,2,3,4,r-1由于对头元素的弹出不影响上式，所以它仍然成立。于是，整个命题就成立了。子定理4 (最后一个子定理)：如果在BFS运行过程中，将vi和vj插入队列，且vi先于vj插入，那么 DISTANCEvi=S(s,v),现在我们要严格证明等号成立。在Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest、Clifford Stein 的 (Introduction to Algorithms Second Edition中在这个地方是运用反证法引出了一个矛盾 来证明命题的，但是我个人觉得不利于大家理解，不会用反证法，我将从我们以前的所证明