前段時間遇到了一些與BFS有關(guān)的有趣的問題,，在一些朋友或者資料的幫助下有所思考,，發(fā)現(xiàn)這個簡單的算法如果能應(yīng)用自如，的確能發(fā)揮強(qiáng)大的功效,，于是乎寫篇博客記錄一下,。

BFS概念很簡單，此處有介紹,；BFS實(shí)現(xiàn)也很簡單,，用一個queue就可以了；而它確實(shí)也是圖中一個非常重要的算法,，而它確實(shí)也可以用來解決一些看似與圖沒啥明顯關(guān)系的問題,。 理解廣度優(yōu)先搜索,，關(guān)鍵在于理解其應(yīng)用。

1. 基本應(yīng)用

廣度優(yōu)先搜索算法是基于圖定義的,，所以最直觀的應(yīng)用自然就在圖中：有明確的vertex和edge,。

比如地圖，某個地點(diǎn)就是vertex,，而連接兩個地點(diǎn)的路徑,，就是edge，假設(shè)edge長度都一樣（當(dāng)然,，事實(shí)上這是不可能的）,，我們就能用廣度優(yōu)先搜索求得兩點(diǎn)間的最短距離；
比如人際關(guān)系圖,，一個人就是vertex,，而兩人是否認(rèn)識（connected） 就是edge，我們熟知的開心網(wǎng),，LinkedIn就是這種情況,，此時我們應(yīng)該可以用廣度優(yōu)先搜索得到兩個人之間最少可以通過幾個朋友取得聯(lián)系。 據(jù)說我們可以通過6個人介紹從而認(rèn)識國家主席 - 不算太壞,。

然而,，有很多問題并不是這么直觀的，你可能看不到一個圖,，看不到BFS的適用性,。此時，我們需要足夠的洞察力,，將問題抽象到一個圖上,，并選擇正確的目標(biāo)函數(shù)來應(yīng)用BFS,。下面幾個例子分別予以說明,。

2. 迷宮問題

迷宮是由一個一個的方格子組成，有些格子之間是相通的,，而有些不是,，把一只小白鼠放入這樣一個迷宮，問小白鼠怎么樣才能最快的走出迷宮

這里迷宮可以用一個簡單的二維數(shù)組來表示,，數(shù)組元素值1表示連通,，0表示不連通。 這雖然不是一個直接的圖的問題,，但其實(shí)也不難看出其和圖的相關(guān)性：

vertex：所有值為1的格子,。 （值為0的格子因?yàn)椴贿B通，從邏輯上來講并不屬于這個圖,，但我們依賴與它來判斷兩點(diǎn)間是否有edge存在）
edge： 任意兩個相鄰的,，且值都為1的vertex之間的聯(lián)系

可以發(fā)現(xiàn),，迷宮的這種對于圖的表達(dá)方式，與傳統(tǒng)的鄰接表,，鄰接矩陣表達(dá)方式很不相同 （更加緊湊）,，但是卻非常適合來表示迷宮這樣的結(jié)構(gòu)。這也是一個圖,，只不過有其特定的訪問方式而已,。 指定起點(diǎn)，與終點(diǎn)（任何邊界vertex）,， 在這個數(shù)組上應(yīng)用BFS,，就能找出走出迷宮的最短路徑，當(dāng)然,，需要注意的是不能重復(fù)訪問已經(jīng)訪問過的結(jié)點(diǎn),，我們可以直接修改表示迷宮的數(shù)組，如訪問過了就設(shè)為0,，也可以提供一個輔助數(shù)組來標(biāo)記是否訪問過,。

這里有篇文章詳細(xì)的介紹了迷宮問題的解法。

3. 倒酒問題

一個8L杯子裝滿了酒,，有一個一個3L空杯子和一個5L空杯子,，問怎樣才能用最少的次數(shù)倒出4L的酒。（不能倒掉）

這是一個面試中常見的邏輯題,，做到這樣的題,，如果不了解其背后的套路，只是像個沒頭蒼蠅一樣不斷的去嘗試,，倒來倒去可能會花很多時間,，而且不一定是最少的，甚至,，還有可能把自己繞暈,。 

一個解法是把每次倒完后3個杯子中酒的數(shù)量視為一個狀態(tài)，而”倒“的過程則是一個狀態(tài)遷移的過程,，初始狀態(tài)為800,， 狀態(tài)遷移則是把杯子A的酒倒入杯子B，結(jié)果要求要么A為空,，要么B為滿,。 我們可以有如下推理過程：

對于這個推理過程，要注意兩點(diǎn)：

• 一是我采用了“寬度優(yōu)先” 的狀態(tài)遷移過程,，也就是說我的思路過程是從左到右,，然后在每一列上從上到下，這可以保證我找到的是最少的步數(shù)
• 二是對于已經(jīng)出現(xiàn)過的狀態(tài),，我不再處理,，不然問題規(guī)模不會逐漸縮?。ㄈ鐝?00到530后，很自然在擴(kuò)展530的時候,，我還可以倒回去成為800,，但因?yàn)?00出現(xiàn)過，不再處理）

這里,，800-305-332-602-620-125-134這條路線以一步的優(yōu)勢勝出,！

可以看出，這里其實(shí)就是應(yīng)用了廣度優(yōu)先搜索算法,，對于更加復(fù)雜的問題（如5個杯子啥的）,，完成可以編程予以解決。 那么圖在哪里,？
vertex：某個時刻三個杯子中酒的狀態(tài) 
edge：可以通過一次倒酒實(shí)現(xiàn)的從一個狀態(tài)到另外一個狀態(tài)的”遷移“,。

為了標(biāo)志某個狀態(tài)是否訪問過，我們可以用一個大小為1000的數(shù)組來表示,，默認(rèn)值為0,，某時刻的狀態(tài)數(shù)值為數(shù)組下標(biāo)，也即100*a + 10*b + c,。（思考,，如果有杯子容量大于10呢？）

(感謝atyuwen同學(xué)給出了這個思路)

有了這樣的思路,，對于解決下面這個過橋問題應(yīng)該比較容易了：

四個女人過橋,，夜間有一火把，每次最多過兩個,，必需帶火把,，過橋速度不一樣 1min, 2min, 5min, 10min; 兩個人過用最慢一個的速度，火把不能扔,，如何在最快的時間內(nèi)讓四個女人都過橋,？

這個問題可以通過思考來解決，原則就是盡量讓快的人在一起,，慢的人在一起,，避免快的被慢的人拖累（這和多線程的負(fù)載平衡類似），這樣解法就是：

• 1, 2過去1回來：3
• 5,，10過去2回來：12
• 1，2過去：2 

17分鐘,，但是如果人比較多的話,，你可能也無法確定是不是最快了。 這個問題其實(shí)也可以用圖的BFS算法解決：
vertex: 在對面的人的狀態(tài),，可以用一個4位的二進(jìn)制數(shù)表示,，沒一為分別對應(yīng)一個人的狀態(tài),，0000表示一個都沒過去，1111表示都過去了
edge：兩個人走過去,，如果還沒全過去的話,，再一個人回來，從而發(fā)生的狀態(tài)“遷移”

這樣,，算法應(yīng)該不難出來了。

4. 連連看

這其實(shí)是《編程之美》第一章”1.14 連連看游戲設(shè)計“中介紹的一個算法,，連連看可以由一個二維數(shù)組表示,，數(shù)組元素的值表示不同的圖形，我們可以用0表示該位置沒有圖形,。 連連看中兩個結(jié)點(diǎn)能夠相連從而消去的標(biāo)準(zhǔn)是：相連不超過兩個彎的相同圖形：
 

（圖片取自編程之美）

這個問題的結(jié)構(gòu)與迷宮問題有點(diǎn)類似,，可是為了應(yīng)用BFS，我們的大腦也得轉(zhuǎn)個彎,，玩家依次點(diǎn)了兩個結(jié)點(diǎn)后,，我們需要判斷是否可以消去：

• 圖形是否相等非常簡單，只要判斷該處元素的值即可
• 相連是否不超過兩個彎,，我們需要從中取一個結(jié)點(diǎn)為起始點(diǎn),，先拿到無須轉(zhuǎn)彎就能到達(dá)的結(jié)點(diǎn)集合A，看目標(biāo)結(jié)點(diǎn)是否在里面,；如果不在,，則需要對結(jié)點(diǎn)集合A中所有結(jié)點(diǎn)，拿到其無須轉(zhuǎn)彎就能到達(dá)的結(jié)點(diǎn)（未在之前訪問過）,，判斷目標(biāo)結(jié)點(diǎn)是否在內(nèi),；如果不在，則繼續(xù)擴(kuò)展,，這次如果再不在,，說明兩結(jié)點(diǎn)連接超過兩個彎了，不滿足

此處, vertex是所有沒有圖形的結(jié)點(diǎn),，而edge則是任意兩個在同一直線上的,，未被有圖形的結(jié)點(diǎn)截斷的結(jié)點(diǎn)之間的聯(lián)系。BFS的應(yīng)用在于結(jié)點(diǎn)距離不超過2次,，此處距離是指轉(zhuǎn)彎次數(shù),。

通過上訴例子，BFS之強(qiáng)大與有趣可見一斑,！