5.2　廣度優(yōu)先遍歷

相對(duì)于DFS來(lái)說(shuō)，BFS的變種比較少，能解決的問(wèn)題種類比較單一。

BFS比較適合用來(lái)找最短距離，因此如果題目中提到了最短距離，首先應(yīng)該想到使用BFS。

使用BFS進(jìn)行解題的思路同樣是定義起始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)，從起點(diǎn)開(kāi)始不斷深入其他節(jié)點(diǎn)，在搜索的過(guò)程中判斷是否滿足特定條件。BFS和DFS只是遍歷的方向不同，即上面提到的DFS是盡可能深地搜索樹(shù)的分支，而B(niǎo)FS則是一層一層地訪問(wèn)節(jié)點(diǎn)。隊(duì)列可以幫我們實(shí)現(xiàn)“一層一層地訪問(wèn)節(jié)點(diǎn)”的效果。其本質(zhì)就是不斷訪問(wèn)鄰居，把鄰居逐個(gè)加入隊(duì)列，根據(jù)隊(duì)列先進(jìn)先出的特點(diǎn)，把每一層節(jié)點(diǎn)訪問(wèn)完后，會(huì)繼續(xù)訪問(wèn)下一層節(jié)點(diǎn)。

偽代碼如下。

小提示：如果是在帶權(quán)圖上進(jìn)行BFS，則可以考慮使用優(yōu)先隊(duì)列來(lái)完成。

接下來(lái)，我們通過(guò)力扣（LeetCode）中的路徑和問(wèn)題、島嶼和問(wèn)題來(lái)詳細(xì)講解DFS和BFS的思路。