寬度優(yōu)先搜索 BFS

1、寬度優(yōu)先搜索BFS寬度優(yōu)先搜索算法(又稱廣度優(yōu)先搜索)是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖 的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。已知圖G=(V,E)和一個源頂點s，寬度優(yōu)先搜索以一種系統(tǒng)的方式探尋G的邊，從而“發(fā)現(xiàn)”s所能到 達的所有頂點，并計算s到所有這些頂點的距離(最少邊數(shù))，該算法同時能生成一棵根為s且包括所有可 達頂點的寬度優(yōu)先樹。對從s可達的任意頂點v，寬度優(yōu)先樹中從s到v的路徑對應(yīng)于圖G中從s到v的 最短路徑，即包含最小邊數(shù)的路徑。該算法對有向圖和無向圖同樣適用。之所以稱之為寬度優(yōu)先算法，是因為算法

2、自始至終一直通過已找到和末找到頂點之間的邊界向外擴 展，就是說，算法首先搜索和s距離為k的所有頂點，然后再去搜索和S距離為k+l的其他頂點。為了保持搜索的軌跡，寬度優(yōu)先搜索為每個頂點著色：白色、灰色或黑色。算法開始前所有頂點都是 白色，隨著搜索的進行，各頂點會逐漸變成灰色，然后成為黑色。在搜索中第一次碰到一頂點時，我們說 該頂點被發(fā)現(xiàn)，此時該頂點變?yōu)榉前咨旤c。因此，灰色和黑色頂點都已被發(fā)現(xiàn)，但是，寬度優(yōu)先搜索算 法對它們加以區(qū)分以保證搜索以寬度優(yōu)先的方式執(zhí)行。若(u,v)E且頂點u為黑色，那么頂點v要么是灰 色，要么是黑色，就是說，所有和黑色頂點鄰接的頂點都已被發(fā)現(xiàn)?；疑旤c可以與一些白色頂

3、點相鄰接， 它們代表著已找到和未找到頂點之間的邊界。在寬度優(yōu)先搜索過程中建立了一棵寬度優(yōu)先樹，起始時只包含根節(jié)點，即源頂點s.在掃描已發(fā)現(xiàn)頂點 u的鄰接表的過程中每發(fā)現(xiàn)一個白色頂點v，該頂點v及邊(u,v)就被添加到樹中。在寬度優(yōu)先樹中，我們 稱結(jié)點u是結(jié)點v的先輩或父母結(jié)點。因為一個結(jié)點至多只能被發(fā)現(xiàn)一次，因此它最多只能有-個父母結(jié) 點。相對根結(jié)點來說祖先和后裔關(guān)系的定義和通常一樣：如果u處于樹中從根s到結(jié)點v的路徑中，那么 u稱為v的祖先，v是u的后裔。下面的寬度優(yōu)先搜索過程BFS假定輸入圖G=(V,E)采用鄰接表表示，對于圖中的每個頂點還采用了 幾種附加的數(shù)據(jù)結(jié)構(gòu)，對每個頂點uV，其色彩

4、存儲于變量coloru中，結(jié)點u的父母存于變量nu中。 如果u沒有父母(例如u=s或u還沒有被檢索到)，則nu=NIL，由算法算出的源點s和頂點u之間的距 離存于變量du中，算法中使用了一個先進先出隊列Q來存放灰色節(jié)點集合。其中headQ表示隊列Q的 隊頭元素，Enqueue(Q,v)表示將元素v入隊，Dequeue(Q)表示對頭元素出隊；Adju表示圖中和u相鄰 的節(jié)點集合。procedure BFS(G,S);beginfor 每個節(jié)點 uEVG-s dobegincoloruWhite;du8；nu-NIL;end;colorsGray;ds-0;nsNIL;Q-swhile Q知 do

5、beginuheadQ;for每個節(jié)點 vEAdju doif colorv=White thenbegincolorvGray;dvdv+1;nvu;Enqueue(Q,v);end;Dequeue(Q);coloruBlack;end;end;圖1展示了用BFS在例圖上的搜索過程。黑色邊是由BFS產(chǎn)生的樹枝。每個節(jié)點u內(nèi)的值為du, 圖中所示的隊列Q是第9-18行while循環(huán)中每次迭代起始時的隊列。隊列中每個結(jié)點下面是該結(jié)點與源 結(jié)點的距離。圖1 BFS在一個無向圖上的執(zhí)行過程過程BFS按如下方式執(zhí)行，第1-4行置每個結(jié)點為白色，置du為無窮大，每個結(jié)點的父母置為 NIL,第5行置源結(jié)點

6、S為灰色，即意味著過程開始時源結(jié)點已被發(fā)現(xiàn)。第6行初始化ds為0，第7行 置源結(jié)點的父母結(jié)點為NIL，第8行初始化隊列0，使其僅含源結(jié)點s，以后Q隊列中僅包含灰色結(jié)點的 集合。程序的主循環(huán)在9-18行中，只要隊列Q中還有灰色結(jié)點，即那些已被發(fā)現(xiàn)但還沒有完全搜索其鄰接 表的結(jié)點，循環(huán)將一直進行下去。第10行確定隊列頭的灰色結(jié)點為u。第11-16行的循環(huán)考察u的鄰接 表中的每一個頂點v。如果v是白色結(jié)點，那么該結(jié)點還沒有被發(fā)現(xiàn)過，算法通過執(zhí)行第13-16行發(fā)現(xiàn)該 結(jié)點。首先它被置為灰色，距離dv置為du+1,而后u被記為該節(jié)點的父母，最后它被放在隊列Q的隊 尾。當結(jié)點u的鄰接表中的所有結(jié)點都被檢索

7、后，第17-18行使u彈出隊列并置成黑色。分析在證明寬度優(yōu)先搜索的各種性質(zhì)之前，我們先做一些相對簡單的工作一分析算法在圖G=(V,E)之上 的運行時間。在初始化后，再沒有任何結(jié)點又被置為白色。因此第12行的測試保證每個結(jié)點至多只能迸 人隊列一次，因而至多只能彈出隊列一次。入隊和出隊操作需要O(1)的時間，因此隊列操作所占用的全部 時間為O(V)，因為只有當每個頂點將被彈出隊列時才會查找其鄰接表，因此每個頂點的鄰接表至多被掃描 一次。因為所有鄰接表的長度和為Q(E)，所以掃描所有鄰接表所花費時間至多為O(E)。初始化操作的開 銷為O(V)，因此過程BFS的全部運行時間為O(V+E)，由此可見，寬

8、度優(yōu)先搜索的運行時間是圖的鄰接 表大小的一個線性函數(shù)。最短路徑在本部分的開始，我們講過，對于一個圖G=(V,E)，寬度優(yōu)先搜索算法可以得到從已知源結(jié)點sV 到每個可達結(jié)點的距離，我們定義最短路徑長度6(s,v)為從頂點s到頂點v的路徑中具有最少邊數(shù)的路徑 所包含的邊數(shù)，若從s到v沒有通路則為。具有這一距離6(s,v)的路徑即為從s到v的最短路徑(后文 我們將把最短路徑推廣到賦權(quán)圖，其中每邊都有一個實型的權(quán)值，一條路徑的權(quán)是組成該路徑所有邊的權(quán) 值之和，目前討論的圖都不是賦權(quán)圖)。在證明寬度優(yōu)先搜索計算出的就是最短路徑長度之前，我們先看 一下最短路徑長度的一個重要性質(zhì)。引理1設(shè)G=(V,E)是一

9、個有向圖或無向圖，sV為G的任意一個結(jié)點，則對任意邊(u,v)eE,6(s,v)6(s,v)0證明：我們對一個頂點進入隊列Q的次數(shù)進行歸納，我們歸納前假設(shè)在所有頂點veV，dv6(s,v)成立。歸納的基礎(chǔ)是BFS過程第8行當結(jié)點s被放入隊列Q后的情形，這時歸納假設(shè)成立，因為對于任意 結(jié)點 veV-s),ds=0=6(s,s)且 dv=6(s,v)0然后進行歸納，考慮從頂點u開始的搜索中發(fā)現(xiàn)一白色頂點v,按歸納假設(shè)，du6(s,u)。從過程第 14行的賦值語句以及引理1可知dv=du+16(s,u)+16(s,v)然后，結(jié)點v被插入隊列Q中。它不會再次被插入隊列，因為它已被置為灰色，而第13-1

10、6行的then 子句只對白色結(jié)點進行操作，這樣dv 的值就不會改變，所以歸納假設(shè)成立。為了證明dv=6(s,v)，首先我們必須更精確地展示在BFS執(zhí)行過程中是如何對隊列進行操作的，下 面一個引理說明無論何時，隊列中的結(jié)點至多有兩個不同的d值。引理3假設(shè)過程BFS在圖G=(V,E)之上的執(zhí)行過程中，隊列Q包含如下結(jié)點，其中v1是隊列Q 的頭，vr是隊列的尾，則 dv.dv1+1 且 dv.dv.+1, i=1,2,.,r-10證明：證明過程是對隊列操作的次數(shù)進行歸納。初始時，隊列僅包含頂點s，引理自然正確。下面進行歸納，我們必須證明在壓入和彈出一個頂點后引理仍然成立。如果隊列的頭七被彈出隊列，

11、新的隊頭為v2(如果此時隊列為空，引理無疑成立)，所以有dvrdv1+1dv2+1,余下的不等式依然成立， 因此v2為隊頭時引理成立。要插入一個結(jié)點入隊列需仔細分析過程BFS，在BFS的第16行，當頂點v 加入隊列成為時，隊列頭v1實際上就是正在掃描其鄰接表的頂E，因此有dv 1=dv=du+1=dv1+1,這時同樣有 dvdv1+1=du+1=dv=dv 1，余下的不等式 dv6(s,v)=-，根據(jù)過程第14行，頂點v不可 能有一個有限的dv值，由歸納可知，不可能有滿足下列條件的第一個頂點存在：該頂點的d值被過程的 第14行語句置為嘰 因此僅對有有限d值的頂點，第14行語句才會被執(zhí)行。所以若

12、v是不可達的話，它 將不會在搜索中被發(fā)現(xiàn)。證明主要是對由s可達的頂點來說的。設(shè)Vk表示和s距離為k的頂點集合，即Vk=veV:O(s,v)=k。 證明過程為對k進行歸納。作為歸納假設(shè)，我們假定對于每一個頂點veVk，在BFS的執(zhí)行中只有某一特 定時刻滿足：-結(jié)點v為灰色；dv被置為k； 如果v手s，則對于某個ue Vki，nv被置為u；v被插入隊列Q中；正如我們先前所述，至多只有一個特定時刻滿足上述條件。歸納的初始情形為k=0，此時V0=s，因為顯然源結(jié)點s是唯一和s距離為0的結(jié)點，在初始化過程 中，s被置為灰色，ds被置為0，且s被放人隊列Q中，所以歸納假設(shè)成立。下面進行歸納，我們須注意除非

13、到算法終止，隊列Q不為空，而且一旦某結(jié)點u被插入隊列，du 和nu都不再改變。根據(jù)引理3可知如果在算法過程中結(jié)點按次序vl,v2,.,vr被插入隊列，那么相應(yīng)的距 離序列是單調(diào)遞增的：dv.10根據(jù)單調(diào)性和dvk(由引理2)和歸納假設(shè)，可知如果v能夠被 發(fā)現(xiàn)，則必在vk-1中的所有結(jié)點進入隊列之后。由6(s,v)=k，可知從s到v有一條具有k邊的通路，因此必存在某結(jié)點u e Vk1，且(u,v)E。不失一 般性，設(shè)u是滿足條件的第一個灰色節(jié)點(根據(jù)歸納可知集合Vk1中的所有結(jié)點都被置為灰色)，BFS把每 一個灰色結(jié)點放入隊列中，這樣由第10行可知結(jié)點u最終必然會作為隊頭出現(xiàn)。當已成為隊頭時，它

14、的 鄰接表將被掃描就會發(fā)現(xiàn)結(jié)點v (結(jié)點v不可能在此之前被發(fā)現(xiàn)，因為它不與V.(jk-1)中的任何結(jié)點相鄰 接，否則v不可能屬于Vk，并且根據(jù)假定，u是和v相鄰接的Vk1中被發(fā)現(xiàn)的第一個結(jié)點)。第13行置v 為灰色，第14行置dv=du+l=k，第 15行置nv為u，第16行把插入隊列中。由于v是Vk中的任意 結(jié)點，因此證明歸納假設(shè)成立。在結(jié)束定理的證明前，我們注意到如果veVk，則據(jù)我們所知可得nveVk1,這樣我們就得到了一 條從s到v的最短路徑：即為從s到nv的最短路徑再通過邊(nv,v)。寬度優(yōu)先樹過程BFS在搜索圖的同時建立了一棵寬度優(yōu)先樹，如圖1所示，這棵樹是由每個結(jié)點的n域所表示

15、。 我們正式定義先輩子圖如下，對于圖G=(V,E)，源頂點為s，其先輩子圖Gn=(Vn,En)滿足：Vn=veV:nv#NILUs且E 尸(nv,v)eE:veVn-s如果V由從s可達的頂點構(gòu)成，那么先輩子圖Gn是一棵寬度優(yōu)先樹，并且對于所有veVn，Gn中 唯一的由s到v的簡單路徑也同樣是G中從s到v的一條最短路徑。由于它互相連通，且|E |=|V |-1(由樹 的性質(zhì))，所以寬度優(yōu)先樹事實上就是一棵樹，En中的邊稱為樹枝。當BFS從圖G的源結(jié)點s開始執(zhí)行后，下面的引理說明先輩子圖是一棵寬度優(yōu)先樹。引理4當過程BFS應(yīng)用于某一有向或無向圖G=(V,E)時，該過程同時建立的n域滿足條件：其先輩子圖 Gn=(Vn,En)是一棵寬度優(yōu)先樹。證明：過程BFS的第15行語句對(u,v)eE且6(s,v)-(即v從s可達)置nv=u，因此V是由V中從v可 達的頂點所組成，由于Gn形成一棵樹，所以它包含從s到V中每一結(jié)點的唯一路徑，由定理1進行歸納， 我們可知其每條路徑都是一條最短路徑。(證畢)下面的過程將打印出從S到v的最短路徑