什么是 BFS？
Breadth First Search (BFS) 寬度優(yōu)先搜索叶摄，又稱廣度優(yōu)先搜索属韧，是圖搜索算法中的一種，與 Depth First Search (DFS) 深度優(yōu)先搜索一起蛤吓，是面試中非常高頻且重要的算法之一宵喂。
BFS 顧名思義，我們搜索的過(guò)程是平鋪開進(jìn)行搜索会傲，即從起點(diǎn)開始锅棕，將所有和它相鄰的結(jié)點(diǎn)都搜索一遍拙泽，然后再一個(gè)個(gè)去搜索這些相鄰結(jié)點(diǎn)自己的相鄰節(jié)點(diǎn)，一層一層鋪開裸燎，從而進(jìn)行搜索顾瞻。其搜索過(guò)程就像水中的漣漪，從中心開始德绿，向四周進(jìn)行擴(kuò)散荷荤，直到遍歷完整個(gè)圖。
BFS 為什么需要隊(duì)列移稳？
對(duì)于 BFS 算法蕴纳，正如上面所說(shuō)的，我們需要一層一層遍歷所有的相鄰結(jié)點(diǎn)个粱。那么相鄰結(jié)點(diǎn)之間的先后順序如何確定古毛？因此我們需要一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行存儲(chǔ)和操作，需要使得先遍歷的結(jié)點(diǎn)先被存儲(chǔ)几蜻，直到當(dāng)前層都被存儲(chǔ)后喇潘，按照先后順序，先被存儲(chǔ)的結(jié)點(diǎn)也會(huì)被先取出來(lái)梭稚，繼續(xù)遍歷它的相鄰結(jié)點(diǎn)颖低。
<figcaption>圖上的 BFS 搜索</figcaption>
因此我們可以發(fā)現(xiàn)，這個(gè)需求不就是我們的隊(duì)列嗎弧烤，First In First Out (FIFO) 完全契合這里的 use case忱屑。因此對(duì)于 BFS 我們需要使用 Queue 這樣的一個(gè)數(shù)據(jù)結(jié)構(gòu)，來(lái)存儲(chǔ)每一層的結(jié)點(diǎn)暇昂，同時(shí)維護(hù)『先進(jìn)先出 FIFO』的順序莺戒。
BFS 算法過(guò)程
BFS 的實(shí)現(xiàn)過(guò)程也非常直接，主要由 3 部分組成：
- 起始：將起點(diǎn)（源點(diǎn)急波，樹的根節(jié)點(diǎn)）放入隊(duì)列中
- 擴(kuò)散：從隊(duì)列中取出隊(duì)頭的結(jié)點(diǎn)从铲，將它的相鄰結(jié)點(diǎn)放入隊(duì)列，不斷重復(fù)這一步
- 終止：當(dāng)隊(duì)列為空時(shí)澄暮，說(shuō)明我們遍歷了所有的結(jié)點(diǎn)名段，整個(gè)圖都被搜索了一遍
下面我們以二維圖的 BFS 搜索過(guò)程，詳細(xì)圖解討論一下 BFS 的過(guò)程泣懊。
2D Matrix 上的 BFS
一般二維圖會(huì)用 2D Matrix 來(lái)表示伸辟，我們可以將二維矩陣進(jìn)行抽象 modelling：
- 將每一個(gè)元素看作結(jié)點(diǎn)（Vertex）
- 每一個(gè)元素和相鄰的上下左右四個(gè)方向的元素中間有一條邊（Edge）
因此，我們將矩陣上的搜索轉(zhuǎn)換為圖上的搜索馍刮。
對(duì)于這個(gè)圖信夫，是一個(gè)簡(jiǎn)單圖，每一條邊的權(quán)重 weight 都是 1，且每條邊都是無(wú)向邊静稻。對(duì)于簡(jiǎn)單圖警没，我們可以用 BFS 來(lái)尋找最短路徑的長(zhǎng)度。下面我們以這副圖為例振湾，來(lái)看一下我們?nèi)绾瓮ㄟ^(guò) BFS 來(lái)找到起始點(diǎn) 1 到終點(diǎn) 9的最短距離惠奸。
為了避免歧義，這里注釋一下恰梢。圖中黃色表示已經(jīng)搜索遍歷過(guò)的結(jié)點(diǎn)佛南，紅色表示現(xiàn)在正在搜索的結(jié)點(diǎn)，粉色表示當(dāng)前層的結(jié)點(diǎn)嵌言，綠色表示從當(dāng)前層結(jié)點(diǎn)出發(fā)搜索到的相鄰結(jié)點(diǎn)嗅回，即下一層的結(jié)點(diǎn)。下面我們來(lái)圖解一下整個(gè)過(guò)程摧茴。
初始化搜索
首先绵载，queue.offer(M[0][0]) 我們先將起始點(diǎn)加入空隊(duì)列中，同時(shí)我們初始化我們的層數(shù) level = 1苛白，開始第一層的搜索娃豹。
接下來(lái)按照算法，我們需要不斷從隊(duì)首取出來(lái)元素购裙，然后去搜索它的相鄰結(jié)點(diǎn)懂版。
第 0 層的搜索
首先通過(guò) queue.poll() 得到當(dāng)前的結(jié)點(diǎn)。
接下來(lái)將 M[0][0] 的上下左右四個(gè)相鄰結(jié)點(diǎn)加入到隊(duì)列中：
由于 1 的左和上都會(huì)出界躏率，沒(méi)有元素躯畴，因此添加完 2 和 7 后，就完成了當(dāng)前層的搜索薇芝。此時(shí) level 為 1蓬抄，表示 2 和 7 距離起點(diǎn) 1 只有 1 層，距離為 1夯到。更新層數(shù) level++嚷缭。
現(xiàn)在我們處理完了第 0 層的結(jié)點(diǎn)，要開始處理第一層的結(jié)點(diǎn)耍贾。但是由于在第二層時(shí)我們還會(huì)在『找鄰居』的過(guò)程中找到第一層的結(jié)點(diǎn)阅爽，加入隊(duì)列，從而進(jìn)行了重復(fù)搜索逼争，因此我們需要一種方法來(lái)標(biāo)記某些結(jié)點(diǎn)被訪問(wèn)過(guò)优床。
一般我們使用一個(gè)和矩陣相同大小的二維 boolean array visited 來(lái)進(jìn)行 mark劝赔。每次找到一個(gè)鄰居時(shí)誓焦，先標(biāo)記該位置為『已訪問(wèn)過(guò)』，visited[x][y] = true，再將鄰居放入隊(duì)列中杂伟。
第 1 層結(jié)點(diǎn)的搜索
接下來(lái)我們發(fā)現(xiàn)了另一個(gè)問(wèn)題移层，對(duì)于第 0 層只有一個(gè)結(jié)點(diǎn)，我們不需要注意赫粥。但是現(xiàn)在第 1 層有兩個(gè)結(jié)點(diǎn)观话，我們如何知道隊(duì)列中哪些是第 1 層的結(jié)點(diǎn)，哪些是搜索得到的下一層的結(jié)點(diǎn)呢越平？
int size = queue.size()
我們可以在搜索當(dāng)前層之前频蛔，獲得當(dāng)前隊(duì)列的大小，因?yàn)?strong>當(dāng)前狀態(tài)下隊(duì)列中的元素都是當(dāng)前層的結(jié)點(diǎn)秦叛。通過(guò)隊(duì)列的 size 進(jìn)行限制晦溪，從而將當(dāng)前層 poll 的次數(shù)限制在 size 次，從而區(qū)分開當(dāng)前層和下一層的結(jié)點(diǎn)挣跋。
將 2 的相鄰結(jié)點(diǎn) 3 和 8 放入隊(duì)列三圆，1 由于已經(jīng)訪問(wèn)過(guò)了，不會(huì)再加入隊(duì)列中避咆。
接下來(lái)處理當(dāng)前層的第二個(gè)結(jié)點(diǎn) 7舟肉，由于 7 也是當(dāng)前層的最后一個(gè)結(jié)點(diǎn)，因此當(dāng)它被從隊(duì)列中 poll 出來(lái)后查库，隊(duì)列中就全都是下一層的結(jié)點(diǎn)了路媚。
由于 8 已經(jīng)被訪問(wèn)過(guò)了，也不會(huì)再重復(fù)放入隊(duì)列中樊销，當(dāng)把 13 放入隊(duì)列后磷籍，當(dāng)前層的搜索也已經(jīng)結(jié)束。此時(shí) level = 2 表示 2 和 7 到起點(diǎn)的距離是 2现柠，更新層數(shù) level++院领。
結(jié)束
對(duì)于最后一層，我們從 3 開始搜索鄰居够吩，當(dāng)我們遇到 9 的時(shí)候比然，我們找到了終點(diǎn)，因此搜索結(jié)束周循。
此時(shí) level 值為 3强法，表示終點(diǎn) 9 到起點(diǎn) 1 的距離為 3，也就是我們最后的答案湾笛。
對(duì)于整個(gè)搜索過(guò)程可以看下面的視頻：
<iframe title="video" src="https://video.zhihu.com/video/1361277881042296833?player=%7B%22shouldShowPageFullScreenButton%22%3Atrue%7D" allowfullscreen="" class="css-uwwqev" frameborder="0"></iframe>
BFS搜索過(guò)程
代碼
下面來(lái)看一下代碼饮怯，正如我們前面所討論的，我們使用了 size 以及 level 兩個(gè)變量來(lái)維護(hù)搜索過(guò)程中的當(dāng)前層以及當(dāng)前層到起點(diǎn)的距離嚎研，以及使用 visited 數(shù)組進(jìn)行標(biāo)記訪問(wèn)過(guò)的結(jié)點(diǎn)避免重復(fù)訪問(wèn)蓖墅。
代碼非常簡(jiǎn)單，一目了然：
這里我們使用了自定義的 Class Cell 來(lái)表示每一個(gè)結(jié)點(diǎn)的橫坐標(biāo)和縱坐標(biāo)，我們也可以使用一個(gè)長(zhǎng)度為 2 的數(shù)組來(lái)表示论矾，index 0 表示 x教翩，index 1 表示 y。
