BFS算法原理和生成樹性質(zhì)證明

1、BFS算法基本思想和證明以及廣度優(yōu)先樹最重要的還有實現(xiàn)張季倫本來想直接寫證明的，這篇文章的最初主題是證明在無權(quán)圖下BFS所產(chǎn)生的生成樹中由起點（根節(jié)點）到任意可達節(jié)點的通路（軌道）都是起點到該節(jié)點的最短路徑?？墒呛髞戆l(fā)現(xiàn)我們的教材實在是對BFS原理和復雜度證明得很少，往往只是寫寫偽代碼然后對復雜度一筆帶過，所以干脆這次連同BFS的原理和復雜度一起寫出來分享。在這之前，大家至少需要看得懂以C為借鑒所寫的偽代碼，以及需要對圖論的基礎知識有一點了解。對于對數(shù)據(jù)結(jié)構(gòu)有了解的同學來說，很容易知道我們一般用鄰接表或者鄰接矩陣以及十字矩陣來實現(xiàn)圖的數(shù)據(jù)結(jié)構(gòu)。今天在這里我用鄰接矩陣實現(xiàn)。這次也準備放出完整調(diào)試

2、后源碼給大家參考，語言是C和C+混編的。Part 1.BFS原理分析：首先，廣度優(yōu)先搜索算法的目的是探索一個未知連通結(jié)構(gòu)的圖，并把這個圖的連通性通過其他數(shù)據(jù)導出。下面來描述一下BFS算法的基本流程。前期工作：為了使BFS運行工作更加流暢和有條理，我們?yōu)樗惴ńY(jié)構(gòu)添加如下輔助數(shù)據(jù)量。1. 向量 COLORELEMETS_NUMBER: 長度為結(jié)點個數(shù)的向量，用于標明即時結(jié)點與已遍歷范圍的相對位置。2. 父節(jié)點向量SUPERELEMENTS_NUMBER:長度同上，數(shù)據(jù)類型為索引類型，標明某一結(jié)點的父節(jié)點位置。3. 通路距離向量DISTANCEELEMENTS_NUM:標識在確定的一個BFS運行實例

3、中起點結(jié)點到其他結(jié)點的距離。4. 輔助隊列QUEUE:為了為待遍歷的節(jié)點提供緩沖。算法開始：這時表示以鄰接矩陣表示的圖的相關邊的數(shù)據(jù)和起點索引已經(jīng)傳入方法。（令索引為index）第一步：初始化將所有節(jié)點的COLOR值置為white。將所有節(jié)點的SUPER值置為-1。將所有節(jié)點的DISTANCE值置為INF。將COLORindex置為Gray。將SUPERindex置為-1。將DISTANCEindex置為0。執(zhí)行enQueue（start index）。第二步：循環(huán)不變式工作如果隊列不為空，則從隊列中彈出一個索引元素temp，對它做以下工作：考察與temp索引指向節(jié)點的所連通的所有節(jié)點，然后對

4、所有有聯(lián)通的并且顏色不是黑色的節(jié)點做以下修改：1. 將所有與temp聯(lián)通節(jié)點的COLOR向量對應值置為Gray。2. 將所有與temp聯(lián)通節(jié)點的SUPER值置為temp。3. 將所有與temp聯(lián)通節(jié)點的DISTANCE對應值設為DISTANCEtemp+1。4. 將所有與temp聯(lián)通節(jié)點的壓入隊列。最后將temp節(jié)點的COLOR值COLORtemp置為black。以上就是BFS的運行流程，下面來解釋一下下。BFS的主要思想是它引入了標記變量“顏色COLOR”來標識節(jié)點的遍歷狀態(tài)。我們定義，當一個節(jié)點沒有被BFS算法發(fā)現(xiàn)時，它是白色的；當一個節(jié)點被發(fā)現(xiàn)，而它的子節(jié)點沒有被發(fā)現(xiàn)時，它是灰色的；當一

5、個節(jié)點被發(fā)現(xiàn)并且它的子節(jié)點也被發(fā)現(xiàn)了，他就是黑色的。這里的父子節(jié)點意思是代表一種發(fā)現(xiàn)順序上的時間關系，如果節(jié)點A和B連通，且A先于B被發(fā)現(xiàn)，那么我們說A節(jié)點是B節(jié)點的父節(jié)點。簡單的說來，黑色節(jié)點是出于已遍歷范圍內(nèi)部的；灰色節(jié)點是出于已遍歷和未遍歷的節(jié)點的分界線；白色節(jié)點是在已遍歷范圍之外的。如圖：（其實這個圖是有特殊性的，為什么我不用普遍性的圖呢？那要等我們證明完以后的問題才知道）我們對黑色節(jié)點和灰色節(jié)點已經(jīng)了解了它們的局部結(jié)構(gòu)，而對于位置連通性的白色節(jié)點，它們在這一個確定的狀態(tài)里相當于是游離的。BFS算法要求給出一個起點，從這個起點開始對所有的節(jié)點遍歷探索；于是，在算法開始時，我們將這個起點

6、壓入隊列，將他的顏色設為灰色，因為此時他的外圍全部都是未被發(fā)現(xiàn)的節(jié)點。同樣，對于父節(jié)（前驅(qū)）點數(shù)組和距離數(shù)組（設定相應的值起點沒有父節(jié)點，起點到起點的距離為一）。接下來，只要隊列不為空，就一直從隊列中彈出節(jié)點元素，并對這個元素做操作；首先，我們考察與這個元素連通且不是黑色的所有節(jié)點，然后對這些節(jié)點相應的數(shù)據(jù)做更新。例如：將這些節(jié)點的顏色置為灰色，因為在他們被發(fā)現(xiàn)后，它們變成了遍歷范圍的邊界；它們到起點的距離被置為彈出元素到起點距離加一；它們的父節(jié)點被設定為彈出的這個元素；最后他們都被壓入隊列；然后我們把當前彈出的這個節(jié)點的顏色設置為黑色，因為在與他聯(lián)通的子節(jié)點都被發(fā)現(xiàn)后，他就退回到遍歷范圍內(nèi)部

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語句就一直執(zhí)行；而在while語句內(nèi)部有一個for each語句，可能大家覺得這個for each 需要分析分析，其實不然，for each只是給出了所有與一個節(jié)點相鄰的節(jié)點，這個東西是線性的。從全局來看，我們會對除了S節(jié)點之外的所有節(jié)點至多做一次COLOR WHITE操作，至多一次COLOR GRAY操作，至多一次COLOR BLACK操作，加上各自的SUPER和DISTANCE操作，而這些操作都是常數(shù)級別的，所以整個算法的時間開銷是關于節(jié)點個數(shù)的線性級別的。源碼在這里（原諒我用這么風騷的色調(diào)，這個對眼睛很好）：首先

10、是公共變量，常量：然后是indexQueue類的實現(xiàn)（一個專門設計用于存儲數(shù)組索引的隊列）：然后是BFS主方法，以及一個遞歸的尋路算法（這個和我們一會兒證明的東西有很大關系）以及一個簡易的main：Part 2.BFS生成最短路徑的完整證明（從最最初條件開始）：BFS算法在完成了之后，假定從起點到某一節(jié)點的邊數(shù)為K，這是又BFS生成的一條通路。有一個事實是，如果我們讓起點和終點不變，一定不能找出另一條通路，使這另一條通路的邊數(shù)小于BFS原來生成的那一條通路。簡單地說，BFS生成的任意連通路徑在無權(quán)圖的條件下都是最短的。下面我們要來證明它，這是Dijstra算法的一個思想，而Dijstra算法的

11、目的就是找出兩給定節(jié)點的最短連通路徑。下面我們的證明過程將是形式化以及條件比較嚴密的：定義：我們定義符號S（）。S（s，v）表示s到v所有可行路徑中的最少邊數(shù)路徑。你可以看到，實際上我們討論的是路徑的邊數(shù)問題，當然，再無權(quán)圖的情況下，邊數(shù)和最優(yōu)權(quán)是一回事。子定理1：假設G=（V,E）是一個圖，s為G的一個節(jié)點（頂點），對于某一條邊（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不是聯(lián)通的，那么不管s和v到連不連通，命題也都是成立的。再來看看我們的證明邏輯，如果我們要想證明BFS的生成路徑（DISTANCEv）是最短距離，那么我們就要至少證明S（s，v）和DIATANCEv,或者說S（s，v）<DIATANCEv。我們要讓DISTANCEv成為S（s，v）的上界才可以。子定理2：假設G=（V,E）是一圖，我們針對某一起點頂點s運行BFS算法，那么在算法運行完成后，對于任意其他節(jié)點，BFS所生成的DISTANCEn，都存在：DISTANCEv>=S(s,v)要證明這個式子，需要從緩沖隊列這個地方入手，我們要討論隊列在每個狀況下這個式子成立與否。1） .

13、初狀態(tài)：我們來看看起點s被壓入隊列之后的情況，由于此時其他節(jié)點的distance值均為INF（無限大，未被發(fā)現(xiàn)），而distances的值為0；所以：DISTANCEs=0>S(s,s)=0DISTANCEV-s=INF>=S(s,v)于是式子成立。2) .普遍狀態(tài)：假設現(xiàn)在BFS開始了對某一結(jié)點u的遍歷，發(fā)現(xiàn)了與u連通的一個節(jié)點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、結(jié)果就明了了：DISTANCEu+1=DISTANCEv>=S(s,u)+1>=S(s,v)于是命題仍然成立。在分析復雜度時提到，一個節(jié)點至多被壓入隊列一次，至多被彈出隊列一次，所以說普遍狀態(tài)對于每一個被新發(fā)現(xiàn)的節(jié)點只會運行一次。于是整個命題就得證了。子定理3:這一個關于各個節(jié)點入隊列順序的證明。命題：如果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均為下標證明：我們還是按照隊列的狀態(tài)來證明命題：1) .初始狀態(tài)：當隊列里只有一個節(jié)點s時，可以知道v1與vr相等，那么命題自然成立。2) .普遍狀態(tài)：a) 普遍狀態(tài)意味著在此時我們已經(jīng)承認命題在初始狀態(tài)時成立。b) 其實普遍狀態(tài)的證明就是證明隊列元素在發(fā)生改變之后命題仍然成立。i. 對隊列添加一個元素，命題成立。ii. 對隊列刪除一個元素，命題成立。假設現(xiàn)在BFS算法在遍歷一個節(jié)點v時，出現(xiàn)了以下需要添加節(jié)點的情況：第一種情況是我們在遍歷v時第一次發(fā)現(xiàn)一個新節(jié)點（白色）。于是我們把它添加進隊列。所以這時有：DISTANCEv+1=DISTANCEv（i+1）所

16、以：DISTANCEvi<=DISTANCEv（i+1）成立。第二種情況是我們在對灰色v遍歷了一段時間后，發(fā)現(xiàn)了白色聯(lián)通節(jié)點v1，之后接著又同是發(fā)現(xiàn)了另一個白色節(jié)點v2，于是可以知道v1，v2都是與v連通的節(jié)點。由于既然v1，v2在遍歷v的聯(lián)通節(jié)點時被找到，所以他們的DISTANCE值只會在此處被修改，且有：DISTANCEv+1=DISTANCEv1+DISTANCEv2于是第二種情況仍然成立。假設在BFS主循環(huán)不變式（隊列不為空便執(zhí)行的命令塊）開始時，隊列彈出了一個元素節(jié)點v1然后我們證明剩余的隊列中元素仍然滿足這個命題：重新考察這個彈出了節(jié)點的隊列，其頭節(jié)點為v2，我們現(xiàn)在要分析v

17、2和原先v1的關系，由于v2是后于v1添加的，所以它滿足：DISTANCEv2<=DISTANCEv1+1DISTANCEv1<=DISTANCEv2如果說v1不是我們最初算法的起始節(jié)點s，那么要么v1和v2的距離要么相等要么v2的距離比v1大一。當v1是初始節(jié)點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證明：結(jié)合BFS算法的特征，我們知道要么vi和vj的鏈接節(jié)點是同一個節(jié)點，要么vi是vj的鏈接節(jié)點（通過對vi遍歷找到白色的vj），所以說DISTANCEvi=DISTANCEvj或者DISTANCEvi+1=DISTANCEvj。命題成立。同樣也可用子定理3來證明這個

19、東西。最后的結(jié)論證明，證明廣度優(yōu)先搜索的正確性：廣度優(yōu)先搜索的正確性是這樣描述的，對于一個無權(quán)圖G（V,E），對于一個起始節(jié)點s運行BFS算法，在算法運行完成之后對于每一個屬于V而不是s的節(jié)點v，都存在：DISTANCEv=S(s,v)并且任意一個從s開始除了s之外的可達節(jié)點v都存在s到v的最短路徑一定是s到PARENTv的最短路徑加上(PARENTv，v)。證明：我們在前面已經(jīng)證明了DISTANCEv>=S(s,v)，現(xiàn)在我們要嚴格證明等號成立。在Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest、Clifford Stein的Int

20、roduction to Algorithms Second Edition中在這個地方是運用反證法引出了一個矛盾來證明命題的，但是我個人覺得不利于大家理解，不會用反證法，我將從我們以前的所證明的子定理來證明這個命題。我將用歸納法證明，而歸納的條件就是各個節(jié)點進入隊列的時機和所處位置。首先，我們需要再來確認一下對S標記的定義。S（s，v）表示從s到v所經(jīng)歷的最短邊數(shù)（前提是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)）?，F(xiàn)在，我將一個BFS具體實例和它說操作的圖的各個節(jié)點分類。節(jié)點將被“分層”。具體定義如下：1.同層節(jié)點：在同一個循環(huán)不變式循環(huán)過程中發(fā)現(xiàn)的節(jié)點，對于任意兩個是同層節(jié)點的節(jié)點的v1，v2存在：PARENTv1=PARENTv2，起點s不存在和它同層的節(jié)點，s所在的層只有s一個元素。同層節(jié)點在QUEUE中都是相鄰的。2. 鄰層節(jié)點：如果DISTANCEv1=DISTANCEv2+1的話，那么v1，v2是鄰層節(jié)點。鄰層節(jié)點之間的QUEUE位置關系為：如果v1和v2為鄰層節(jié)點，v1先于v2入隊列，那么：v1和v2相鄰 或者：對于任意一個存在于隊列中且位置在v1和v2之間的節(jié)點vi，那么存在：v2>=DISTANCEvi>=v1 且：當v2>DISTANCEvi成立時，v2=DISTANCEvi+1必然成立。當v1<DISTANCEvi成立時，v1=DISTANCEvi-1必然成立。3. 頭層節(jié)點：s節(jié)點。4. 尾層節(jié)點：對于整個