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

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

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

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

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

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

6、壓入隊(duì)列，將他的顏色設(shè)為灰色，因?yàn)榇藭r(shí)他的外圍全部都是未被發(fā)現(xiàn)的節(jié)點(diǎn)。同樣，對(duì)于父節(jié)（前驅(qū)）點(diǎn)數(shù)組和距離數(shù)組（設(shè)定相應(yīng)的值起點(diǎn)沒有父節(jié)點(diǎn)，起點(diǎn)到起點(diǎn)的距離為一）。接下來，只要隊(duì)列不為空，就一直從隊(duì)列中彈出節(jié)點(diǎn)元素，并對(duì)這個(gè)元素做操作；首先，我們考察與這個(gè)元素連通且不是黑色的所有節(jié)點(diǎn)，然后對(duì)這些節(jié)點(diǎn)相應(yīng)的數(shù)據(jù)做更新。例如：將這些節(jié)點(diǎn)的顏色置為灰色，因?yàn)樵谒麄儽话l(fā)現(xiàn)后，它們變成了遍歷范圍的邊界；它們到起點(diǎn)的距離被置為彈出元素到起點(diǎn)距離加一；它們的父節(jié)點(diǎn)被設(shè)定為彈出的這個(gè)元素；最后他們都被壓入隊(duì)列；然后我們把當(dāng)前彈出的這個(gè)節(jié)點(diǎn)的顏色設(shè)置為黑色，因?yàn)樵谂c他聯(lián)通的子節(jié)點(diǎn)都被發(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;算法復(fù)雜度分析：關(guān)于BFS的時(shí)間復(fù)雜度，其實(shí)用不著用漸進(jìn)方法去分析，我們可以看到

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

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

11、目的就是找出兩給定節(jié)點(diǎn)的最短連通路徑。下面我們的證明過程將是形式化以及條件比較嚴(yán)密的：定義：我們定義符號(hào)S（）。S（s，v）表示s到v所有可行路徑中的最少邊數(shù)路徑。你可以看到，實(shí)際上我們討論的是路徑的邊數(shù)問題，當(dāng)然，再無權(quán)圖的情況下，邊數(shù)和最優(yōu)權(quán)是一回事。子定理1：假設(shè)G=（V,E）是一個(gè)圖，s為G的一個(gè)節(jié)點(diǎn)（頂點(diǎn)），對(duì)于某一條邊（u，v）V，存在：S（s，v）<=S（s，u）+1證明：首先我們知道，如果s定點(diǎn)和u不連通，那么S（s，u）為無限大。試想一下，如果s和u是連通的，那么由于（u,v）V，所以s和v也必然是連通的，這個(gè)時(shí)候命題是成立的（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：假設(shè)G=（V,E）是一圖，我們針對(duì)某一起點(diǎn)頂點(diǎn)s運(yùn)行BFS算法，那么在算法運(yùn)行完成后，對(duì)于任意其他節(jié)點(diǎn)，BFS所生成的DISTANCEn，都存在：DISTANCEv>=S(s,v)要證明這個(gè)式子，需要從緩沖隊(duì)列這個(gè)地方入手，我們要討論隊(duì)列在每個(gè)狀況下這個(gè)式子成立與否。1） .

13、初狀態(tài)：我們來看看起點(diǎn)s被壓入隊(duì)列之后的情況，由于此時(shí)其他節(jié)點(diǎn)的distance值均為INF（無限大，未被發(fā)現(xiàn)），而distances的值為0；所以：DISTANCEs=0>S(s,s)=0DISTANCEV-s=INF>=S(s,v)于是式子成立。2) .普遍狀態(tài)：假設(shè)現(xiàn)在BFS開始了對(duì)某一結(jié)點(diǎn)u的遍歷，發(fā)現(xiàn)了與u連通的一個(gè)節(jié)點(diǎn)v。注意，這時(shí)DISTANCEu>=S(s,u)是成立的。于是有：DISTANCEu>=S(s,u).#0DISTANCEv=DISTANCEu+1.#1子定理1中證明了：S（s，v）<=S（s，u）+1.#2當(dāng)#0,#1和#2合起來時(shí)，

14、結(jié)果就明了了：DISTANCEu+1=DISTANCEv>=S(s,u)+1>=S(s,v)于是命題仍然成立。在分析復(fù)雜度時(shí)提到，一個(gè)節(jié)點(diǎn)至多被壓入隊(duì)列一次，至多被彈出隊(duì)列一次，所以說普遍狀態(tài)對(duì)于每一個(gè)被新發(fā)現(xiàn)的節(jié)點(diǎn)只會(huì)運(yùn)行一次。于是整個(gè)命題就得證了。子定理3:這一個(gè)關(guān)于各個(gè)節(jié)點(diǎn)入隊(duì)列順序的證明。命題：如果QUEUE是G=(V,E)運(yùn)行BFS算法時(shí)所運(yùn)用的輔助隊(duì)列，在QUEUE中包含頂點(diǎn)v1,v2,v3,.,vr，v1為隊(duì)列頭，vr為隊(duì)列尾；那么存在：DISTANCEvr<=DISTANCEv1+1且DISTANCEvi<=DISTANCEv（i+1）i=1,2,3,4

15、,.,r-1注意：i，r，i+1均為下標(biāo)證明：我們還是按照隊(duì)列的狀態(tài)來證明命題：1) .初始狀態(tài)：當(dāng)隊(duì)列里只有一個(gè)節(jié)點(diǎn)s時(shí)，可以知道v1與vr相等，那么命題自然成立。2) .普遍狀態(tài)：a) 普遍狀態(tài)意味著在此時(shí)我們已經(jīng)承認(rèn)命題在初始狀態(tài)時(shí)成立。b) 其實(shí)普遍狀態(tài)的證明就是證明隊(duì)列元素在發(fā)生改變之后命題仍然成立。i. 對(duì)隊(duì)列添加一個(gè)元素，命題成立。ii. 對(duì)隊(duì)列刪除一個(gè)元素，命題成立。假設(shè)現(xiàn)在BFS算法在遍歷一個(gè)節(jié)點(diǎn)v時(shí)，出現(xiàn)了以下需要添加節(jié)點(diǎn)的情況：第一種情況是我們在遍歷v時(shí)第一次發(fā)現(xiàn)一個(gè)新節(jié)點(diǎn)（白色）。于是我們把它添加進(jìn)隊(duì)列。所以這時(shí)有：DISTANCEv+1=DISTANCEv（i+1）所

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

17、2和原先v1的關(guān)系，由于v2是后于v1添加的，所以它滿足：DISTANCEv2<=DISTANCEv1+1DISTANCEv1<=DISTANCEv2如果說v1不是我們最初算法的起始節(jié)點(diǎn)s，那么要么v1和v2的距離要么相等要么v2的距離比v1大一。當(dāng)v1是初始節(jié)點(diǎn)s時(shí)，v2距離絕對(duì)比v1大1。、由于：DISTANCEvr<=DISTANCEv1+1DISTANCEv2=DISTANCEv1或者DISTANCEv2=DISTANCEv1+1所以：DISTANCEv2+1>=DISTANCEv1+1>=DISTANCEvr即：DISTANCEv2+1>=DIST

18、ANCEvr而對(duì)于證明：DISTANCEvi<=DISTANCEv（i+1）i=1,2,3,4,.,r-1由于對(duì)頭元素的彈出不影響上式，所以它仍然成立。于是，整個(gè)命題就成立了。子定理4（最后一個(gè)子定理）：如果在BFS運(yùn)行過程中，將vi和vj插入隊(duì)列，且vi先于vj插入，那么DISTANCEvi<=DISTANCEvj證明：結(jié)合BFS算法的特征，我們知道要么vi和vj的鏈接節(jié)點(diǎn)是同一個(gè)節(jié)點(diǎn)，要么vi是vj的鏈接節(jié)點(diǎn)（通過對(duì)vi遍歷找到白色的vj），所以說DISTANCEvi=DISTANCEvj或者DISTANCEvi+1=DISTANCEvj。命題成立。同樣也可用子定理3來證明這個(gè)

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

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