廣度寬度優(yōu)先搜索(bfs)

《廣度寬度優(yōu)先搜索(bfs)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、廣度/寬度優(yōu)先搜索(BFS)【算法入門(mén)】1.前言廣度優(yōu)先搜索（也稱寬度優(yōu)先搜索，縮寫(xiě)B(tài)FS，以下采用廣度來(lái)描述）是連通圖的一種遍歷策略。因?yàn)樗乃枷胧菑囊粋€(gè)頂點(diǎn)V0開(kāi)始，輻射狀地優(yōu)先遍歷其周?chē)^廣的區(qū)域，故得名。一般可以用它做什么呢？一個(gè)最直觀經(jīng)典的例子就是走迷宮，我們從起點(diǎn)開(kāi)始，找出到終點(diǎn)的最短路程，很多最短路徑算法就是基于廣度優(yōu)先的思想成立的。算法導(dǎo)論里邊會(huì)給出不少嚴(yán)格的證明，我想盡量寫(xiě)得通俗一點(diǎn)，因此采用一些直觀的講法來(lái)偽裝成證明，關(guān)鍵的point能夠幫你get到就好。2.圖的概念剛剛說(shuō)的廣度優(yōu)先搜索是連通圖的一種遍歷

2、策略，那就有必要將圖先簡(jiǎn)單解釋一下。圖2-1連通圖示例圖如圖2-1所示，這就是我們所說(shuō)的連通圖，這里展示的是一個(gè)無(wú)向圖，連通即每2個(gè)點(diǎn)都有至少一條路徑相連，例如V0到V4的路徑就是V0->V1->V4。一般我們把頂點(diǎn)用V縮寫(xiě)，把邊用E縮寫(xiě)。3.廣度優(yōu)先搜索3.1.算法的基本思路常常我們有這樣一個(gè)問(wèn)題，從一個(gè)起點(diǎn)開(kāi)始要到一個(gè)終點(diǎn)，我們要找尋一條最短的路徑，從圖2-1舉例，如果我們要求V0到V6的一條最短路（假設(shè)走一個(gè)節(jié)點(diǎn)按一步來(lái)算）【注意：此處你可以選擇不看這段文字直接看圖3-1】，我們明顯看出這條路徑就是V0->V2->V6

3、，而不是V0->V3->V5->V6。先想想你自己剛剛是怎么找到這條路徑的：首先看跟V0直接連接的節(jié)點(diǎn)V1、V2、V3，發(fā)現(xiàn)沒(méi)有V6，進(jìn)而再看剛剛V1、V2、V3的直接連接節(jié)點(diǎn)分別是：{V0、V4}、{V0、V1、V6}、{V0、V1、V5}（這里畫(huà)刪除線的意思是那些頂點(diǎn)在我們剛剛的搜索過(guò)程中已經(jīng)找過(guò)了，我們不需要重新回頭再看他們了）。這時(shí)候我們從V2的連通節(jié)點(diǎn)集中找到了V6，那說(shuō)明我們找到了這條V0到V6的最短路徑：V0->V2->V6，雖然你再進(jìn)一步搜索V5的連接節(jié)點(diǎn)集合后會(huì)找到另一條路徑V0->V3->V5->V6，但

4、顯然他不是最短路徑。你會(huì)看到這里有點(diǎn)像輻射形狀的搜索方式，從一個(gè)節(jié)點(diǎn)，向其旁邊節(jié)點(diǎn)傳遞病毒，就這樣一層一層的傳遞輻射下去，知道目標(biāo)節(jié)點(diǎn)被輻射中了，此時(shí)就已經(jīng)找到了從起點(diǎn)到終點(diǎn)的路徑。我們采用示例圖來(lái)說(shuō)明這個(gè)過(guò)程，在搜索的過(guò)程中，初始所有節(jié)點(diǎn)是白色（代表了所有點(diǎn)都還沒(méi)開(kāi)始搜索），把起點(diǎn)V0標(biāo)志成灰色（表示即將輻射V0），下一步搜索的時(shí)候，我們把所有的灰色節(jié)點(diǎn)訪問(wèn)一次，然后將其變成黑色（表示已經(jīng)被輻射過(guò)了），進(jìn)而再將他們所能到達(dá)的節(jié)點(diǎn)標(biāo)志成灰色（因?yàn)槟切┕?jié)點(diǎn)是下一步搜索的目標(biāo)點(diǎn)了），但是這里有個(gè)判斷，就像剛剛的例子，當(dāng)訪問(wèn)到V1

5、節(jié)點(diǎn)的時(shí)候，它的下一個(gè)節(jié)點(diǎn)應(yīng)該是V0和V4，但是V0已經(jīng)在前面被染成黑色了，所以不會(huì)將它染灰色。這樣持續(xù)下去，直到目標(biāo)節(jié)點(diǎn)V6被染灰色，說(shuō)明了下一步就到終點(diǎn)了，沒(méi)必要再搜索（染色）其他節(jié)點(diǎn)了，此時(shí)可以結(jié)束搜索了，整個(gè)搜索就結(jié)束了。然后根據(jù)搜索過(guò)程，反過(guò)來(lái)把最短路徑找出來(lái)，圖3-1中把最終路徑上的節(jié)點(diǎn)標(biāo)志成綠色。整個(gè)過(guò)程的實(shí)例圖如圖3-1所示。初始全部都是白色（未訪問(wèn)）即將搜索起點(diǎn)V0（灰色）已搜索V0，即將搜索V1、V2、V3……終點(diǎn)V6被染灰色，終止找到最短路徑圖3-1尋找V0到V6的過(guò)程3.2.廣度優(yōu)先搜索流程圖圖3-2

6、廣度優(yōu)先搜索的流程圖在寫(xiě)具體代碼之前有必要先舉個(gè)實(shí)例，詳見(jiàn)第4節(jié)。4.實(shí)例第一節(jié)就講過(guò)廣度優(yōu)先搜索適用于迷宮類問(wèn)題，這里先給出POJ3984《迷宮問(wèn)題》?！睹詫m問(wèn)題》定義一個(gè)二維數(shù)組：intmaze[5][5]={0,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,1,0,};它表示一個(gè)迷宮，其中的1表示墻壁，0表示可以走的路，只能橫著走或豎著走，不能斜著走，要求編程序找出從左上角到右下角的最短路線。題目保證了輸入是一定有解的。也許你會(huì)問(wèn)，這個(gè)跟廣度優(yōu)先搜索的圖怎么對(duì)應(yīng)起來(lái)？BFS的第

7、一步就是要識(shí)別圖的節(jié)點(diǎn)跟邊！4.1.識(shí)別出節(jié)點(diǎn)跟邊節(jié)點(diǎn)就是某種狀態(tài)，邊就是節(jié)點(diǎn)與節(jié)點(diǎn)間的某種規(guī)則。對(duì)應(yīng)于《迷宮問(wèn)題》，你可以這么認(rèn)為，節(jié)點(diǎn)就是迷宮路上的每一個(gè)格子（非墻），走迷宮的時(shí)候，格子間的關(guān)系是什么呢？按照題目意思，我們只能橫豎走，因此我們可以這樣看，格子與它橫豎方向上的格子是有連通關(guān)系的，只要這個(gè)格子跟另一個(gè)格子是連通的，那么兩個(gè)格子節(jié)點(diǎn)間就有一條邊。如果說(shuō)本題再修改成斜方向也可以走的話，那么就是格子跟周?chē)?個(gè)格子都可以連通，于是一個(gè)節(jié)點(diǎn)就會(huì)有8條邊（除了邊界的節(jié)點(diǎn)）。4.2.解題思路對(duì)應(yīng)于題目的輸入數(shù)組：0,1,0

8、,0,0,0,1,0,1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,1,0,我們把節(jié)點(diǎn)定義為(x,y)，(x,y)表示數(shù)組maze的項(xiàng)maze[x][y]。于是起點(diǎn)就是(0,0)，終點(diǎn)是(4,4)。按照剛剛的思路，我們大概手工梳理一遍：初始條件：起點(diǎn)Vs為(0,0)終點(diǎn)Vd為