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

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

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

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

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

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

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

6、廣度優(yōu)先搜索的流程圖在寫具體代碼之前有必要先舉個實例，詳見第4節(jié)。4.實例第一節(jié)就講過廣度優(yōu)先搜索適用于迷宮類問題，這里先給出POJ3984《迷宮問題》?！睹詫m問題》定義一個二維數(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,};它表示一個迷宮，其中的1表示墻壁，0表示可以走的路，只能橫著走或豎著走，不能斜著走，要求編程序找出從左上角到右下角的最短路線。題目保證了輸入是一定有解的。也許你會問，這個跟廣度優(yōu)先搜索的圖怎么對應(yīng)起來？BFS的第

7、一步就是要識別圖的節(jié)點跟邊！4.1.識別出節(jié)點跟邊節(jié)點就是某種狀態(tài)，邊就是節(jié)點與節(jié)點間的某種規(guī)則。對應(yīng)于《迷宮問題》，你可以這么認(rèn)為，節(jié)點就是迷宮路上的每一個格子（非墻），走迷宮的時候，格子間的關(guān)系是什么呢？按照題目意思，我們只能橫豎走，因此我們可以這樣看，格子與它橫豎方向上的格子是有連通關(guān)系的，只要這個格子跟另一個格子是連通的，那么兩個格子節(jié)點間就有一條邊。如果說本題再修改成斜方向也可以走的話，那么就是格子跟周圍8個格子都可以連通，于是一個節(jié)點就會有8條邊（除了邊界的節(jié)點）。4.2.解題思路對應(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é)點定義為(x,y)，(x,y)表示數(shù)組maze的項maze[x][y]。于是起點就是(0,0)，終點是(4,4)。按照剛剛的思路，我們大概手工梳理一遍：初始條件：起點Vs為(0,0)終點Vd為