廣度優(yōu)先遍歷呈現(xiàn)出「一層一層向外擴(kuò)張」的特點(diǎn)啡专，先看到的結(jié)點(diǎn)先遍歷险毁，后看到的結(jié)點(diǎn)后遍歷，因此「廣度優(yōu)先遍歷」可以借助「隊(duì)列」實(shí)現(xiàn)畔况。
我們以二叉樹來舉例鲸鹦，從
根節(jié)點(diǎn)開始，我們將根節(jié)點(diǎn)放入一個(gè)列隊(duì)跷跪，然后開始遍歷列隊(duì)里面的節(jié)點(diǎn)馋嗜，把列隊(duì)中遍歷到的節(jié)點(diǎn)的可達(dá)節(jié)點(diǎn)從左往右的順序紛紛放入到列隊(duì)，當(dāng)遍歷完某一層節(jié)點(diǎn)個(gè)數(shù)的時(shí)候吵瞻，列隊(duì)里面所剩下的節(jié)點(diǎn)就是下一層的節(jié)點(diǎn)葛菇，如此循環(huán)甘磨，直到遍歷完所有節(jié)點(diǎn)或者達(dá)到目標(biāo)節(jié)點(diǎn)。
此時(shí)便是到達(dá)目標(biāo)節(jié)點(diǎn)的最少深度眯停。
下面用一個(gè)題目來舉例：
我們有一個(gè)二叉樹济舆，需要根據(jù)下面的遍歷結(jié)果輸出：
3
/ \
9 20
/ \
15 7
//節(jié)點(diǎn)的結(jié)構(gòu)如下
//給定一個(gè)樹節(jié)點(diǎn)結(jié)構(gòu)
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
需要返回的結(jié)果結(jié)構(gòu)為：
[
[3],
[9,20],
[15,7]
]
思路
- 題目要求我們一層一層輸出樹的結(jié)點(diǎn)的值，很明顯需要使用「廣度優(yōu)先遍歷」實(shí)現(xiàn)莺债；
- 廣度優(yōu)先遍歷借助「隊(duì)列」實(shí)現(xiàn)滋觉；
- 注意子結(jié)點(diǎn)入隊(duì)的時(shí)候，非空的判斷很重要：在隊(duì)列的隊(duì)首元素出隊(duì)的時(shí)候齐邦，>一定要在左（右）子結(jié)點(diǎn)非空的時(shí)候才將左（右）子結(jié)點(diǎn)入隊(duì)椎侠。
- 樹的廣度優(yōu)先遍歷的寫法模式相對(duì)固定：
- 使用隊(duì)列；
- 在隊(duì)列非空的時(shí)候措拇，動(dòng)態(tài)取出隊(duì)首元素我纪；
- 取出隊(duì)首元素的時(shí)候，把隊(duì)首元素相鄰的結(jié)點(diǎn)（非空）加入隊(duì)列儡羔。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
// 注意 1：一定要先把當(dāng)前隊(duì)列的結(jié)點(diǎn)總數(shù)暫存起來
int currentSize = queue.size();
//下面這個(gè)循環(huán)主要用于分層，如果不需要分層汰蜘，則可以不使用這個(gè)循環(huán)
List<Integer> currentLevel = new ArrayList<>();
for (int i = 0; i < currentSize; i++) {
TreeNode front = queue.poll();
currentLevel.add(front.val);
// 注意 2：左（右）孩子結(jié)點(diǎn)非空才加入隊(duì)列
if (front.left != null) {
queue.offer(front.left);
}
if (front.right != null) {
queue.offer(front.right);
}
}
res.add(currentLevel);
}
return res;
}
}
使用廣度優(yōu)先遍歷得到無權(quán)圖的最短路徑
上面舉的例子是一個(gè)二叉樹仇冯，不存在環(huán)苛坚，例如迷宮，是存在交叉口的這種情況需要特別注意：將結(jié)點(diǎn)添加到隊(duì)列以后色难，一定要馬上標(biāo)記為「已經(jīng)訪問」泼舱，否則相同結(jié)點(diǎn)會(huì)重復(fù)入隊(duì)，這一點(diǎn)在初學(xué)的時(shí)候很容易忽略枷莉。
另外一點(diǎn)還需要強(qiáng)調(diào)娇昙，廣度優(yōu)先遍歷用于求解「無權(quán)圖」的最短路徑，因此一定要認(rèn)清「無權(quán)圖」這個(gè)前提條件笤妙。如果是帶權(quán)圖冒掌，就需要使用相應(yīng)的專門的算法去解決它們。事實(shí)上蹲盘，這些「專門」的算法的思想也都基于「廣度優(yōu)先遍歷」的思想股毫，我們?yōu)榇蠹依e如下：
- 帶權(quán)有向圖、且所有權(quán)重都非負(fù)的單源最短路徑問題：使用
Dijkstra算法召衔； - 帶權(quán)有向圖的單源最短路徑問題：
Bellman-Ford算法铃诬； - 一個(gè)圖的所有結(jié)點(diǎn)對(duì)的最短路徑問題：
Floy-Warshall算法。
總結(jié)
廣度優(yōu)先遍歷可以用于「樹」和「圖」的問題的遍歷；
廣度優(yōu)先遍歷作用于「無權(quán)圖」趣席，得到的是「最短路徑」兵志。如果題目有讓求「最小」、「最短」宣肚、「最少」毒姨，可以考慮這個(gè)問題是不是可以建立成一個(gè)「圖形結(jié)構(gòu)」或者「樹形結(jié)構(gòu)」，用「廣度優(yōu)先遍歷」的思想求得「最小」、「最短」、「最少」的數(shù)值梆靖；
廣度優(yōu)先遍歷作用于圖論問題的時(shí)候，結(jié)點(diǎn)在加入隊(duì)列以后標(biāo)記為已經(jīng)訪問俘枫，否則會(huì)出現(xiàn)結(jié)點(diǎn)重復(fù)入隊(duì)的情況。
