广度优先遍历呈现出「一层一层向外扩张」的特点，先看到的结点先遍历，后看到的结点后遍历，因此「广度优先遍历」可以借助「队列」实现。
我们以二叉树来举例，从
根节点开始，我们将根节点放入一个列队，然后开始遍历列队里面的节点，把列队中遍历到的节点的可达节点从左往右的顺序纷纷放入到列队，当遍历完某一层节点个数的时候，列队里面所剩下的节点就是下一层的节点，如此循环，直到遍历完所有节点或者达到目标节点。
此时便是到达目标节点的最少深度。
下面用一个题目来举例：
我们有一个二叉树，需要根据下面的遍历结果输出：
3
/ \
9 20
/ \
15 7
//节点的结构如下
//给定一个树节点结构
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;
}
}
需要返回的结果结构为：
[
[3],
[9,20],
[15,7]
]
思路
- 题目要求我们一层一层输出树的结点的值，很明显需要使用「广度优先遍历」实现；
- 广度优先遍历借助「队列」实现；
- 注意子结点入队的时候，非空的判断很重要：在队列的队首元素出队的时候，>一定要在左（右）子结点非空的时候才将左（右）子结点入队。
- 树的广度优先遍历的写法模式相对固定：
- 使用队列；
- 在队列非空的时候，动态取出队首元素；
- 取出队首元素的时候，把队首元素相邻的结点（非空）加入队列。
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：一定要先把当前队列的结点总数暂存起来
int currentSize = queue.size();
//下面这个循环主要用于分层，如果不需要分层，则可以不使用这个循环
List<Integer> currentLevel = new ArrayList<>();
for (int i = 0; i < currentSize; i++) {
TreeNode front = queue.poll();
currentLevel.add(front.val);
// 注意 2：左（右）孩子结点非空才加入队列
if (front.left != null) {
queue.offer(front.left);
}
if (front.right != null) {
queue.offer(front.right);
}
}
res.add(currentLevel);
}
return res;
}
}
使用广度优先遍历得到无权图的最短路径
上面举的例子是一个二叉树，不存在环，例如迷宫，是存在交叉口的这种情况需要特别注意：将结点添加到队列以后，一定要马上标记为「已经访问」，否则相同结点会重复入队，这一点在初学的时候很容易忽略。
另外一点还需要强调，广度优先遍历用于求解「无权图」的最短路径，因此一定要认清「无权图」这个前提条件。如果是带权图，就需要使用相应的专门的算法去解决它们。事实上，这些「专门」的算法的思想也都基于「广度优先遍历」的思想，我们为大家例举如下：
- 带权有向图、且所有权重都非负的单源最短路径问题：使用
Dijkstra算法； - 带权有向图的单源最短路径问题：
Bellman-Ford算法； - 一个图的所有结点对的最短路径问题：
Floy-Warshall算法。
总结
广度优先遍历可以用于「树」和「图」的问题的遍历；
广度优先遍历作用于「无权图」，得到的是「最短路径」。如果题目有让求「最小」、「最短」、「最少」，可以考虑这个问题是不是可以建立成一个「图形结构」或者「树形结构」，用「广度优先遍历」的思想求得「最小」、「最短」、「最少」的数值；
广度优先遍历作用于图论问题的时候，结点在加入队列以后标记为已经访问，否则会出现结点重复入队的情况。
