广度优先搜索(BFS)
Ⅰ 解题套路
BFS 的核心思想就是把一些问题抽象成图，从一个点开始，向四周开始扩散。一般来说，我们写 BFS 算法都是用「队列」这种数据结构，每次将一个节点周围的所有节点加入队列。BFS 相对 DFS 的最主要的区别是：BFS 找到的路径一定是最短的，但代价就是空间复杂度比 DFS 大很多。
问题的本质就是让你在一幅「图」中找到从起点 start 到终点 target 的最近距离。
解题框架：
队列 q 就不说了，BFS 的核心数据结构；cur.adj() 泛指 cur 相邻的节点，比如说二维数组中，cur 上下左右四面的位置就是相邻节点；visited 的主要作用是防止走回头路，大部分时候都是必须的，但是像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路就不需要 visited。
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
Queue<Node> q; // 核心数据结构
Set<Node> visited; // 避免走回头路
q.offer(start); // 将起点加入队列
visited.add(start);
int step = 0; // 记录扩散的步数
while (q not empty) {
int sz = q.size();
/* 将当前队列中的所有节点向四周扩散 */
for (int i = 0; i < sz; i++) {
Node cur = q.poll();
/* 划重点：这里判断是否到达终点 */
if (cur is target)
return step;
/* 将 cur 的相邻节点加入队列 */
for (Node x : cur.adj())
if (x not in visited) {
q.offer(x);
visited.add(x);
}
}
/* 划重点：更新步数在这里 */
step++;
}
}
Ⅱ 相关习题
1、二叉树的最小深度（LeetCode 111）
BFS 借助队列做到一次一步「齐头并进」，是可以在不遍历完整棵树的条件下找到最短距离的。形象点说，DFS 是线，BFS 是面；DFS 是单打独斗，BFS 是集体行动。
class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
int depth = 1;
Deque<TreeNode> queue = new ArrayDeque<>();
queue.addLast(root);
//由于二叉树的特殊性，不需要加入isvisited数组
while (!queue.isEmpty()) {
int queueSize = queue.size();
//将队列里的所有元素向外扩散一次
for (int i=0;i<queueSize;i++) {
TreeNode removeNode = queue.removeFirst();
//结束条件
if (removeNode.left == null && removeNode.right == null) {
return depth;
}
if (removeNode.left != null) {
queue.addLast(removeNode.left);
}
if (removeNode.right != null) {
queue.addLast(removeNode.right);
}
}
depth++;
}
return -1;
}
}
2、打开转盘锁的次数（LeetCode 752）
第一步，我们不管所有的限制条件，不管 deadends 和 target 的限制，就思考一个问题：如果让你设计一个算法，穷举所有可能的密码组合，你怎么做？穷举呗，再简单一点，如果你只转一下锁，有几种可能？总共有 4 个位置，每个位置可以向上转，也可以向下转，也就是有 8 种可能对吧。
比如说从 "0000" 开始，转一次，可以穷举出 "1000", "9000", "0100", "0900"... 共 8 种密码。然后，再以这 8 种密码作为基础，对每个密码再转一下，穷举出所有可能...仔细想想，这就可以抽象成一幅图，每个节点有 8 个相邻的节点，又让你求最短距离，这不就是典型的 BFS 嘛。
class Solution {
public int openLock(String[] deadends, String target) {
//将deadends转化为HashSet存储
Set<String> dead = new HashSet<>();
for (String str:deadends) {
dead.add(str);
}
//记录访问过的密码
Set<String> isvisited = new HashSet<>();
Deque<String> queue = new ArrayDeque<>();
int step = 0;
queue.addLast("0000");
isvisited.add("0000");
//进行BFS
while (!queue.isEmpty()) {
int queueSize = queue.size();
for (int i=0;i<queueSize;i++) {
String curStr = queue.removeFirst();
if (curStr.equals(target)) {
return step;
}
if (dead.contains(curStr)) {
continue;
}
//穷举所有选择
for (int j=0;j<4;j++) {
String upStr = upRotation(curStr,j);
if (!isvisited.contains(upStr)) {
queue.addLast(upStr);
isvisited.add(upStr);
}
String downStr = downRotation(curStr,j);
if (!isvisited.contains(downStr)) {
queue.addLast(downStr);
isvisited.add(downStr);
}
}
}
//增加步数
step++;
}
//没试出来返回-1
return -1;
}
public String upRotation(String s , int position) {
char[] temp = s.toCharArray();
if (temp[position] == '9') {
temp[position] = '0';
} else {
temp[position] += 1;
}
return new String(temp);
}
public String downRotation(String s , int position) {
char[] temp = s.toCharArray();
if (temp[position] == '0') {
temp[position] = '9';
} else {
temp[position] -= 1;
}
return new String(temp);
}
}
3、二叉树的层序遍历
见树的总结
