廣度/寬度優先搜尋(BFS)
【算法入門】
郭志偉@SYSU：raphealguo(at)qq.com
2012/04/27
1.前言
廣度優先搜尋（也稱寬度優先搜尋，縮寫BFS，以下采用廣度來描述）是連通圖的一種周遊政策。因為它的思想是從一個頂點V0開始，輻射狀地優先周遊其周圍較廣的區域，故得名。
一般可以用它做什麼呢？一個最直覺經典的例子就是走迷宮，我們從起點開始，找出到終點的最短路程，很多最短路徑算法就是基于廣度優先的思想成立的。
算法導論裡邊會給出不少嚴格的證明，我想盡量寫得通俗一點，是以采用一些直覺的講法來僞裝成證明，關鍵的point能夠幫你get到就好。
2.圖的概念
剛剛說的廣度優先搜尋是連通圖的一種周遊政策，那就有必要将圖先簡單解釋一下。
圖2-1 連通圖示例圖
如圖2-1所示，這就是我們所說的連通圖，這裡展示的是一個無向圖，連通即每2個點都有至少一條路徑相連，例如V0到V4的路徑就是V0->V1->V4。
一般我們把頂點用V縮寫，把邊用E縮寫。
3.廣度優先搜尋
3.1.算法的基本思路
常常我們有這樣一個問題，從一個起點開始要到一個終點，我們要找尋一條最短的路徑，從圖2-1舉例，如果我們要求V0到V6的一條最短路（假設走一個節點按一步來算）【注意：此處你可以選擇不看這段文字直接看圖3-1】，我們明顯看出這條路徑就是V0->V2->V6，而不是V0->V3->V5->V6。先想想你自己剛剛是怎麼找到這條路徑的：首先看跟V0直接連接配接的節點V1、V2、V3，發現沒有V6，進而再看剛剛V1、V2、V3的直接連接配接節點分别是：{V0、V4}、{V0、V1、V6}、{V0、V1、V5}（這裡畫删除線的意思是那些頂點在我們剛剛的搜尋過程中已經找過了，我們不需要重新回頭再看他們了）。這時候我們從V2的連通節點集中找到了V6，那說明我們找到了這條V0到V6的最短路徑：V0->V2->V6，雖然你再進一步搜尋V5的連接配接節點集合後會找到另一條路徑V0->V3->V5->V6，但顯然他不是最短路徑。
你會看到這裡有點像輻射形狀的搜尋方式，從一個節點，向其旁邊節點傳遞病毒，就這樣一層一層的傳遞輻射下去，知道目标節點被輻射中了，此時就已經找到了從起點到終點的路徑。
我們采用示例圖來說明這個過程，在搜尋的過程中，初始所有節點是白色（代表了所有點都還沒開始搜尋），把起點V0标志成灰色（表示即将輻射V0），下一步搜尋的時候，我們把所有的灰色節點通路一次，然後将其變成黑色（表示已經被輻射過了），進而再将他們所能到達的節點标志成灰色（因為那些節點是下一步搜尋的目标點了），但是這裡有個判斷，就像剛剛的例子，當通路到V1節點的時候，它的下一個節點應該是V0和V4，但是V0已經在前面被染成黑色了，是以不會将它染灰色。這樣持續下去，直到目标節點V6被染灰色，說明了下一步就到終點了，沒必要再搜尋（染色）其他節點了，此時可以結束搜尋了，整個搜尋就結束了。然後根據搜尋過程，反過來把最短路徑找出來，圖3-1中把最終路徑上的節點标志成綠色。
整個過程的執行個體圖如圖3-1所示。
初始全部都是白色（未通路）
即将搜尋起點V0（灰色）
已搜尋V0，即将搜尋V1、V2、V3
……終點V6被染灰色，終止
找到最短路徑
圖3-1 尋找V0到V6的過程
3.2.廣度優先搜尋流程圖
圖3-2 廣度優先搜尋的流程圖
在寫具體代碼之前有必要先舉個執行個體，詳見第4節。
4.執行個體
第一節就講過廣度優先搜尋适用于迷宮類問題，這裡先給出POJ3984《迷宮問題》。
《迷宮問題》
定義一個二維數組：
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,
};
它表示一個迷宮，其中的1表示牆壁，0表示可以走的路，隻能橫着走或豎着走，不能斜着走，要求程式設計式找出從左上角到右下角的最短路線。
題目保證了輸入是一定有解的。
也許你會問，這個跟廣度優先搜尋的圖怎麼對應起來？BFS的第一步就是要識别圖的節點跟邊！
4.1.識别出節點跟邊
節點就是某種狀态，邊就是節點與節點間的某種規則。
對應于《迷宮問題》，你可以這麼認為，節點就是迷宮路上的每一個格子（非牆），走迷宮的時候，格子間的關系是什麼呢？按照題目意思，我們隻能橫豎走，是以我們可以這樣看，格子與它橫豎方向上的格子是有連通關系的，隻要這個格子跟另一個格子是連通的，那麼兩個格子節點間就有一條邊。
如果說本題再修改成斜方向也可以走的話，那麼就是格子跟周圍8個格子都可以連通，于是一個節點就會有8條邊（除了邊界的節點）。
4.2.解題思路
對應于題目的輸入數組：
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,
我們把節點定義為(x,y)，(x,y)表示數組maze的項maze[x][y]。
于是起點就是(0,0)，終點是(4,4)。按照剛剛的思路，我們大概手工梳理一遍：
初始條件：
起點Vs為(0,0)
終點Vd為(4,4)
灰色節點集合Q={}
初始化所有節點為白色節點
開始我們的廣度搜尋！
手工執行步驟【PS：你可以直接看圖4-1】:
1.起始節點Vs變成灰色，加入隊列Q，Q={(0,0)}
2.取出隊列Q的頭一個節點Vn，Vn={0,0}，Q={}
3.把Vn={0,0}染成黑色，取出Vn所有相鄰的白色節點{(1,0)}
4.不包含終點(4,4)，染成灰色，加入隊列Q，Q={(1,0)}
5.取出隊列Q的頭一個節點Vn，Vn={1,0}，Q={}
6.把Vn={1,0}染成黑色，取出Vn所有相鄰的白色節點{(2,0)}
7.不包含終點(4,4)，染成灰色，加入隊列Q，Q={(2,0)}
8.取出隊列Q的頭一個節點Vn，Vn={2,0}，Q={}
9.把Vn={2,0}染成黑色，取出Vn所有相鄰的白色節點{(2,1), (3,0)}
10.不包含終點(4,4)，染成灰色，加入隊列Q，Q={(2,1), (3,0)}
11.取出隊列Q的頭一個節點Vn，Vn={2,1}，Q={(3,0)}
12. 把Vn={2,1}染成黑色，取出Vn所有相鄰的白色節點{(2,2)}
13.不包含終點(4,4)，染成灰色，加入隊列Q，Q={(3,0), (2,2)}
14.持續下去，知道Vn的所有相鄰的白色節點中包含了(4,4)……
15.此時獲得了答案
起始你很容易模仿上邊過程走到終點，那為什麼它就是最短的呢？
怎麼保證呢？
我們來看看廣度搜尋的過程中節點的順序情況：
圖4-1 迷宮問題的搜尋樹
你是否觀察到了，廣度搜尋的順序是什麼樣子的？
圖中标号即為我們搜尋過程中的順序，我們觀察到，這個搜尋順序是按照上圖的層次關系來的，例如節點(0,0)在第1層，節點(1,0)在第2層，節點(2,0)在第3層，節點(2,1)和節點(3,0)在第3層。
我們的搜尋順序就是第一層->第二層->第三層->第N層這樣子。
我們假設終點在第N層，是以我們搜尋到的路徑長度肯定是N，而且這個N一定是所求最短的。
我們用簡單的反證法來證明：假設終點在第N層上邊出現過，例如第M層，M<N，那麼我們在搜尋的過程中，肯定是先搜尋到第M層的，此時搜尋到第M層的時候發現終點出現過了，那麼最短路徑應該是M，而不是N了。
是以根據廣度優先搜尋的話，搜尋到終點時，該路徑一定是最短的。
4.3.代碼
我給出以下代碼用于解決上述題目(僅僅隻是核心代碼)：
/**
* 廣度優先搜尋
* @param Vs 起點
* @param Vd 終點
*/
bool BFS(Node& Vs, Node& Vd){
queue<Node> Q;
Node Vn, Vw;
int i;
//用于标記顔色當visit[i][j]==true時，說明節點通路過，也就是黑色
bool visit[MAXL][MAXL];
//四個方向
int dir[][2] = {
{0, 1}, {1, 0},
{0, -1}, {-1, 0}
};
//初始狀态将起點放進隊列Q
Q.push(Vs);
visit[Vs.x][Vs.y] = true;//設定節點已經通路過了！
while (!Q.empty()){//隊列不為空，繼續搜尋！
//取出隊列的頭Vn
Vn = Q.front();
Q.pop();
for(i = 0; i < 4; ++i){
Vw = Node(Vn.x+dir[i][0], Vn.y+dir[i][1]);//計算相鄰節點
if (Vw == Vd){//找到終點了！
//把路徑記錄，這裡沒給出解法
return true;//傳回
}
if (isValid(Vw) && !visit[Vw.x][Vw.y]){
//Vw是一個合法的節點并且為白色節點
Q.push(Vw);//加入隊列Q
visit[Vw.x][Vw.y] = true;//設定節點顔色
}
}
}
return false;//無解
}
5.核心代碼
為了友善适用于大多數的題解，抽取核心代碼如下：
/**
* 廣度優先搜尋
* @param Vs 起點
* @param Vd 終點
*/
bool BFS(Node& Vs, Node& Vd){
queue<Node> Q;
Node Vn, Vw;
int i;
//初始狀态将起點放進隊列Q
Q.push(Vs);
hash(Vw) = true;//設定節點已經通路過了！
while (!Q.empty()){//隊列不為空，繼續搜尋！
//取出隊列的頭Vn
Vn = Q.front();
//從隊列中移除
Q.pop();
while(Vw = Vn通過某規則能夠到達的節點){
if (Vw == Vd){//找到終點了！
//把路徑記錄，這裡沒給出解法
return true;//傳回
}
if (isValid(Vw) && !visit[Vw]){
//Vw是一個合法的節點并且為白色節點
Q.push(Vw);//加入隊列Q
hash(Vw) = true;//設定節點顔色
}
}
}
return false;//無解
}
對于一個題目來說，要标志節點是否通路過，用數組是一種很快速的方法，但有時資料量太大，很難用一個大數組來記錄時，采用hash是最好的做法。實際上visit數組在這裡也是充當hash的作用。（PS：至于hash是什麼？得自己去了解，它的作用是在O(1)的時間複雜度内取出某個值）
6.其他執行個體
6.1.題目描述
給定序列1 2 3 4 5 6，再給定一個k，我們給出這樣的操作：對于序列，我們可以将其中k個連續的數全部反轉過來，例如k = 3的時候，上述序列經過1步操作後可以變成：3 2 1 4 5 6 ，如果再對序列 3 2 1 4 5 6進行一步操作，可以變成3 4 1 2 5 6.
那麼現在題目就是，給定初始序列，以及結束序列，以及k的值，那麼你能夠求出從初始序列到結束序列的轉變至少需要幾步操作嗎？
6.2.思路
本題可以采用BFS求解，已經給定初始狀态跟目标狀态，要求之間的最短操作，其實也很明顯是用BFS了。
我們把每次操作完的序列當做一個狀态節點。那每一次操作就産生一條邊，這個操作就是規則。
假設起始節點是：{1 2 3 4 5 6}，終點是：{3 4 1 2 5 6}
去除隊列中的起始節點時，将它的相鄰節點加入隊列，其相鄰節點就是對其操作一次的所有序列：
{3 2 1 4 5 6}、{1 4 3 2 5 6}、{1 2 5 4 3 6}、{1 2 3 6 5 4}
然後繼續搜尋即可得到終點，此時操作數就是搜尋到的節點所在的層數2。
7.OJ題目
題目分類來自網絡：
sicily：1048 1444 1215 1135 1150 1151 1114
pku：1136 1249 1028 1191 3278 1426 3126 3087 3414
8.總結
假設圖有V個頂點，E條邊，廣度優先搜尋算法需要搜尋V個節點，是以這裡的消耗是O(V)，在搜尋過程中，又需要根據邊來增加隊列的長度，于是這裡需要消耗O(E)，總得來說，效率大約是O(V+E)。
其實最影響BFS算法的是在于Hash運算，我們前面給出了一個visit數組，已經算是最快的Hash了，但有些題目來說可能Hash的速度要退化到O(lgn)的複雜度，當然了，具體還是看實際情況的。
BFS适合此類題目：給定初始狀态跟目标狀态，要求從初始狀态到目标狀态的最短路徑。
9.擴充
進而擴充的話就是雙向廣度搜尋算法，顧名思義，即是從起點跟終點分别做廣度優先搜尋，直到他們的搜尋過程中有一個節點相同了，于是就找到了起點跟終點的一條路徑。
騰訊筆試題目：假設每個人平均是有25個好友，根據六維理論，任何人之間的聯系一定可以通過6個人而間接認識，間接通過N個人認識的，那他就是你的N度好友，現在要你程式設計驗證這個6維理論。
此題如果直接做廣度優先搜尋，那麼搜尋的節點數可能達到25^6，如果是用雙向的話，兩個樹分别隻需要搜尋到3度好友即可，搜尋節點最多為25^3個，但是用雙向廣度算法的話會有一個問題要解決，就是你如何在搜尋的過程中判斷第一棵樹中的節點跟第二棵樹中的節點有相同的呢？按我的了解，可以用Hash，又或者放進隊列的元素都是指向原來節點的指針，而每個節點加入一個color的屬性，這樣再搜尋過程中就可以根據節點的color來判斷是否已經被搜尋過了。
=========================================================
本文為原創，轉載請注明出處：[email protected]：http://blog.csdn.net/raphealguo
作者：raphealguo(at)qq.com
時間：2012/04/27