轉(zhuǎn)自：https://blog.csdn.net/raphealguo/article/details/7523411
1.前言
廣度優(yōu)先搜索（也稱寬度優(yōu)先搜索，縮寫B(tài)FS，以下采用廣度來描述）是連通圖的一種遍歷策略。因?yàn)樗乃枷胧菑囊粋€(gè)頂點(diǎn)V0開始，輻射狀地優(yōu)先遍歷其周圍較廣的區(qū)域，故得名。?
一般可以用它做什么呢？一個(gè)最直觀經(jīng)典的例子就是走迷宮，我們從起點(diǎn)開始，找出到終點(diǎn)的最短路程，很多最短路徑算法就是基于廣度優(yōu)先的思想成立的。
算法導(dǎo)論里邊會(huì)給出不少嚴(yán)格的證明，我想盡量寫得通俗一點(diǎn)，因此采用一些直觀的講法來偽裝成證明，關(guān)鍵的point能夠幫你get到就好。
2.圖的概念
剛剛說的廣度優(yōu)先搜索是連通圖的一種遍歷策略，那就有必要將圖先簡單解釋一下。
如圖2-1所示，這就是我們所說的連通圖，這里展示的是一個(gè)無向圖，連通即每2個(gè)點(diǎn)都有至少一條路徑相連，例如V0到V4的路徑就是V0->V1->V4。
一般我們把頂點(diǎn)用V縮寫，把邊用E縮寫。
3.廣度優(yōu)先搜索
3.1.算法的基本思路
常常我們有這樣一個(gè)問題，從一個(gè)起點(diǎn)開始要到一個(gè)終點(diǎn)，我們要找尋一條最短的路徑，從圖2-1舉例，如果我們要求V0到V6的一條最短路（假設(shè)走一個(gè)節(jié)點(diǎn)按一步來算）【注意：此處你可以選擇不看這段文字直接看圖3-1】，我們明顯看出這條路徑就是V0->V2->V6，而不是V0->V3->V5->V6。先想想你自己剛剛是怎么找到這條路徑的：首先看跟V0直接連接的節(jié)點(diǎn)V1、V2、V3，發(fā)現(xiàn)沒有V6，進(jìn)而再看剛剛V1、V2、V3的直接連接節(jié)點(diǎn)分別是：{V0、V4}、{V0、V1、V6}、{V0、V1、V5}（這里畫刪除線的意思是那些頂點(diǎn)在我們剛剛的搜索過程中已經(jīng)找過了，我們不需要重新回頭再看他們了）。這時(shí)候我們從V2的連通節(jié)點(diǎn)集中找到了V6，那說明我們找到了這條V0到V6的最短路徑：V0->V2->V6，雖然你再進(jìn)一步搜索V5的連接節(jié)點(diǎn)集合后會(huì)找到另一條路徑V0->V3->V5->V6，但顯然他不是最短路徑。
你會(huì)看到這里有點(diǎn)像輻射形狀的搜索方式，從一個(gè)節(jié)點(diǎn)，向其旁邊節(jié)點(diǎn)傳遞病毒，就這樣一層一層的傳遞輻射下去，知道目標(biāo)節(jié)點(diǎn)被輻射中了，此時(shí)就已經(jīng)找到了從起點(diǎn)到終點(diǎn)的路徑。
我們采用示例圖來說明這個(gè)過程，在搜索的過程中，初始所有節(jié)點(diǎn)是白色（代表了所有點(diǎn)都還沒開始搜索），把起點(diǎn)V0標(biāo)志成灰色（表示即將輻射V0），下一步搜索的時(shí)候，我們把所有的灰色節(jié)點(diǎn)訪問一次，然后將其變成黑色（表示已經(jīng)被輻射過了），進(jìn)而再將他們所能到達(dá)的節(jié)點(diǎn)標(biāo)志成灰色（因?yàn)槟切┕?jié)點(diǎn)是下一步搜索的目標(biāo)點(diǎn)了），但是這里有個(gè)判斷，就像剛剛的例子，當(dāng)訪問到V1節(jié)點(diǎn)的時(shí)候，它的下一個(gè)節(jié)點(diǎn)應(yīng)該是V0和V4，但是V0已經(jīng)在前面被染成黑色了，所以不會(huì)將它染灰色。這樣持續(xù)下去，直到目標(biāo)節(jié)點(diǎn)V6被染灰色，說明了下一步就到終點(diǎn)了，沒必要再搜索（染色）其他節(jié)點(diǎn)了，此時(shí)可以結(jié)束搜索了，整個(gè)搜索就結(jié)束了。然后根據(jù)搜索過程，反過來把最短路徑找出來，圖3-1中把最終路徑上的節(jié)點(diǎn)標(biāo)志成綠色。
整個(gè)過程的實(shí)例圖如圖3-1所示。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?圖3-1?尋找V0到V6的過程?
3.2.廣度優(yōu)先搜索流程圖
在寫具體代碼之前有必要先舉個(gè)實(shí)例，詳見第4節(jié)。
4.實(shí)例
第一節(jié)就講過廣度優(yōu)先搜索適用于迷宮類問題，這里先給出POJ3984《迷宮問題》。
《迷宮問題》
定義一個(gè)二維數(shù)組：?
int?maze[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ì)問，這個(gè)跟廣度優(yōu)先搜索的圖怎么對(duì)應(yīng)起來？BFS的第一步就是要識(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)于《迷宮問題》，你可以這么認(rèn)為，節(jié)點(diǎn)就是迷宮路上的每一個(gè)格子（非墻），走迷宮的時(shí)候，格子間的關(guān)系是什么呢？按照題目意思，我們只能橫豎走，因此我們可以這樣看，格子與它橫豎方向上的格子是有連通關(guān)系的，只要這個(gè)格子跟另一個(gè)格子是連通的，那么兩個(gè)格子節(jié)點(diǎn)間就有一條邊。
如果說本題再修改成斜方向也可以走的話，那么就是格子跟周圍8個(gè)格子都可以連通，于是一個(gè)節(jié)點(diǎn)就會(huì)有8條邊（除了邊界的節(jié)點(diǎn)）。
4.2.解題思路
對(duì)應(yīng)于題目的輸入數(shù)組：
? ? 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,
我們把節(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為(4,4)
灰色節(jié)點(diǎn)集合Q={}
初始化所有節(jié)點(diǎn)為白色節(jié)點(diǎn)
開始我們的廣度搜索！
手工執(zhí)行步驟【PS：你可以直接看圖4-1】:
1.起始節(jié)點(diǎn)Vs變成灰色，加入隊(duì)列Q，Q={(0,0)}
2.取出隊(duì)列Q的頭一個(gè)節(jié)點(diǎn)Vn，Vn={0,0}，Q={}
3.把Vn={0,0}染成黑色，取出Vn所有相鄰的白色節(jié)點(diǎn){(1,0)}
4.不包含終點(diǎn)(4,4)，染成灰色，加入隊(duì)列Q，Q={(1,0)}
5.取出隊(duì)列Q的頭一個(gè)節(jié)點(diǎn)Vn，Vn={1,0}，Q={}
6.把Vn={1,0}染成黑色，取出Vn所有相鄰的白色節(jié)點(diǎn){(2,0)}
7.不包含終點(diǎn)(4,4)，染成灰色，加入隊(duì)列Q，Q={(2,0)}
8.取出隊(duì)列Q的頭一個(gè)節(jié)點(diǎn)Vn，Vn={2,0}，Q={}
9.把Vn={2,0}染成黑色，取出Vn所有相鄰的白色節(jié)點(diǎn){(2,1),?(3,0)}
10.不包含終點(diǎn)(4,4)，染成灰色，加入隊(duì)列Q，Q={(2,1),?(3,0)}
11.取出隊(duì)列Q的頭一個(gè)節(jié)點(diǎn)Vn，Vn={2,1}，Q={(3,0)}
12. 把Vn={2,1}染成黑色，取出Vn所有相鄰的白色節(jié)點(diǎn){(2,2)}
13.不包含終點(diǎn)(4,4)，染成灰色，加入隊(duì)列Q，Q={(3,0),?(2,2)}
14.持續(xù)下去，知道Vn的所有相鄰的白色節(jié)點(diǎn)中包含了(4,4)……
15.此時(shí)獲得了答案
起始你很容易模仿上邊過程走到終點(diǎn)，那為什么它就是最短的呢？
怎么保證呢？
我們來看看廣度搜索的過程中節(jié)點(diǎn)的順序情況：
你是否觀察到了，廣度搜索的順序是什么樣子的？
圖中標(biāo)號(hào)即為我們搜索過程中的順序，我們觀察到，這個(gè)搜索順序是按照上圖的層次關(guān)系來的，例如節(jié)點(diǎn)(0,0)在第1層，節(jié)點(diǎn)(1,0)在第2層，節(jié)點(diǎn)(2,0)在第3層，節(jié)點(diǎn)(2,1)和節(jié)點(diǎn)(3,0)在第3層。
我們的搜索順序就是第一層->第二層->第三層->第N層這樣子。
我們假設(shè)終點(diǎn)在第N層，因此我們搜索到的路徑長度肯定是N，而且這個(gè)N一定是所求最短的。
我們用簡單的反證法來證明：假設(shè)終點(diǎn)在第N層上邊出現(xiàn)過，例如第M層，M<N，那么我們?cè)谒阉鞯倪^程中，肯定是先搜索到第M層的，此時(shí)搜索到第M層的時(shí)候發(fā)現(xiàn)終點(diǎn)出現(xiàn)過了，那么最短路徑應(yīng)該是M，而不是N了。
所以根據(jù)廣度優(yōu)先搜索的話，搜索到終點(diǎn)時(shí)，該路徑一定是最短的。
4.3.代碼
我給出以下代碼用于解決上述題目(僅僅只是核心代碼)：
沒有用Python就不列了
5.核心代碼
為了方便適用于大多數(shù)的題解，抽取核心代碼如下：
沒有用Python就不列了
對(duì)于一個(gè)題目來說，要標(biāo)志節(jié)點(diǎn)是否訪問過，用數(shù)組是一種很快速的方法，但有時(shí)數(shù)據(jù)量太大，很難用一個(gè)大數(shù)組來記錄時(shí)，采用hash是最好的做法。實(shí)際上visit數(shù)組在這里也是充當(dāng)hash的作用。（PS：至于hash是什么？得自己去了解，它的作用是在O(1)的時(shí)間復(fù)雜度內(nèi)取出某個(gè)值）
6.其他實(shí)例
6.1.題目描述
給定序列1?2?3?4?5?6，再給定一個(gè)k，我們給出這樣的操作：對(duì)于序列，我們可以將其中k個(gè)連續(xù)的數(shù)全部反轉(zhuǎn)過來，例如k?=?3的時(shí)候，上述序列經(jīng)過1步操作后可以變成：3?2?1?4?5?6?，如果再對(duì)序列?3?2?1?4?5?6進(jìn)行一步操作，可以變成3?4?1?2?5?6.
那么現(xiàn)在題目就是，給定初始序列，以及結(jié)束序列，以及k的值，那么你能夠求出從初始序列到結(jié)束序列的轉(zhuǎn)變至少需要幾步操作嗎？
6.2.思路
本題可以采用BFS求解，已經(jīng)給定初始狀態(tài)跟目標(biāo)狀態(tài)，要求之間的最短操作，其實(shí)也很明顯是用BFS了。
我們把每次操作完的序列當(dāng)做一個(gè)狀態(tài)節(jié)點(diǎn)。那每一次操作就產(chǎn)生一條邊，這個(gè)操作就是規(guī)則。
假設(shè)起始節(jié)點(diǎn)是：{1?2?3?4?5?6}，終點(diǎn)是：{3?4?1?2?5?6}
去除隊(duì)列中的起始節(jié)點(diǎn)時(shí)，將它的相鄰節(jié)點(diǎn)加入隊(duì)列，其相鄰節(jié)點(diǎn)就是對(duì)其操作一次的所有序列：
{3?2?1?4?5?6}、{1?4?3?2?5?6}、{1?2?5?4?3?6}、{1?2?3?6?5?4}
然后繼續(xù)搜索即可得到終點(diǎn)，此時(shí)操作數(shù)就是搜索到的節(jié)點(diǎn)所在的層數(shù)2。
7.OJ題目
題目分類來自網(wǎng)絡(luò)：
sicily：1048?1444?1215?1135?1150?1151?1114
pku：1136?1249?1028?1191?3278?1426?3126?3087?3414?
8.總結(jié)
假設(shè)圖有V個(gè)頂點(diǎn)，E條邊，廣度優(yōu)先搜索算法需要搜索V個(gè)節(jié)點(diǎn)，因此這里的消耗是O(V)，在搜索過程中，又需要根據(jù)邊來增加隊(duì)列的長度，于是這里需要消耗O(E)，總得來說，效率大約是O(V+E)。
其實(shí)最影響B(tài)FS算法的是在于Hash運(yùn)算，我們前面給出了一個(gè)visit數(shù)組，已經(jīng)算是最快的Hash了，但有些題目來說可能Hash的速度要退化到O(lgn)的復(fù)雜度，當(dāng)然了，具體還是看實(shí)際情況的。
BFS適合此類題目：給定初始狀態(tài)跟目標(biāo)狀態(tài)，要求從初始狀態(tài)到目標(biāo)狀態(tài)的最短路徑。
9.擴(kuò)展
進(jìn)而擴(kuò)展的話就是雙向廣度搜索算法，顧名思義，即是從起點(diǎn)跟終點(diǎn)分別做廣度優(yōu)先搜索，直到他們的搜索過程中有一個(gè)節(jié)點(diǎn)相同了，于是就找到了起點(diǎn)跟終點(diǎn)的一條路徑。
騰訊筆試題目：假設(shè)每個(gè)人平均是有25個(gè)好友，根據(jù)六維理論，任何人之間的聯(lián)系一定可以通過6個(gè)人而間接認(rèn)識(shí)，間接通過N個(gè)人認(rèn)識(shí)的，那他就是你的N度好友，現(xiàn)在要你編程驗(yàn)證這個(gè)6維理論。
此題如果直接做廣度優(yōu)先搜索，那么搜索的節(jié)點(diǎn)數(shù)可能達(dá)到25^6，如果是用雙向的話，兩個(gè)樹分別只需要搜索到3度好友即可，搜索節(jié)點(diǎn)最多為25^3個(gè)，但是用雙向廣度算法的話會(huì)有一個(gè)問題要解決，就是你如何在搜索的過程中判斷第一棵樹中的節(jié)點(diǎn)跟第二棵樹中的節(jié)點(diǎn)有相同的呢？按我的理解，可以用Hash，又或者放進(jìn)隊(duì)列的元素都是指向原來節(jié)點(diǎn)的指針，而每個(gè)節(jié)點(diǎn)加入一個(gè)color的屬性，這樣再搜索過程中就可以根據(jù)節(jié)點(diǎn)的color來判斷是否已經(jīng)被搜索過了。
---------------------
作者：raphealguo
來源：CSDN
原文：https://blog.csdn.net/raphealguo/article/details/7523411
版權(quán)聲明：本文為博主原創(chuàng)文章，轉(zhuǎn)載請(qǐng)附上博文鏈接！
