BFS框架：
// 计算从起点 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++;
}
}
队列 q 就不说了，BFS 的核心数据结构；cur.adj() 泛指 cur 相邻的节点，比如说二维数组中，cur 上下左右四面的位置就是相邻节点；visited 的主要作用是防止走回头路，大部分时候都是必须的，但是像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路就不需要 visited。
1.打开转盘锁
题目描述：
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。
代码题解：
class Solution {
public int openLock(String[] deadends, String target) {
Queue<String> q = new LinkedList<>();
q.offer("0000");
// 记录转动过的数字，防止走回头路
Set<String> visited = new HashSet<>();
// 记录需要跳过的死亡密码
Set<String> deads = new HashSet<>();
for(String s:deadends) {
deads.add(s);
}
visited.add("0000");
// 从起点开始启动广度优先搜索
int dep = 0;
while(!q.isEmpty()) {
int size = q.size();
/* 将当前队列中的所有节点向周围扩散 */
for(int i=0; i<size;i++) {
String cur = q.poll();
if(cur.equals(target)) {
return dep;
}
if(deads.contains(cur)) {
continue;
}
/* 将一个节点的未遍历相邻的八个节点加入队列 */
for(int j=0;j<4;j++) {
String up = plusOne(cur,j);
if(!visited.contains(up)) {
visited.add(up);
q.offer(up);
}
String down = minusOne(cur,j);
if(!visited.contains(down)) {
visited.add(down);
q.offer(down);
}
}
}
dep++;
}
return -1;
}
String plusOne(String s,int j) {
//往上波动
char[] ch = s.toCharArray();
if(ch[j] == '9') {
ch[j] ='0';
}else {
ch[j] +=1;
}
return new String(ch);
}
String minusOne(String s,int j) {
//向下波动
char[] ch = s.toCharArray();
if(ch[j] == '0') {
ch[j] = '9';
}else {
ch[j]-=1;
}
return new String(ch);
}
}
双向BFS解法：
class Solution {
public int openLock(String[] deadends, String target) {
//双向BFS
// 用集合不用队列，可以快速判断元素是否存在
Set<String> q1 = new HashSet<>();
Set<String> q2 = new HashSet<>();
Set<String> visited = new HashSet<>();
Set<String> deads = new HashSet<>();
for(String s:deadends) {
deads.add(s);
}
//起点
q1.add("0000");
// 终点
q2.add(target);
int dep = 0;
while(!q1.isEmpty()&&!q2.isEmpty()) {
// 哈希集合在遍历的过程中不能修改，用 temp 存储扩散结果
Set<String> temp = new HashSet<>();
/* 将 q1 中的所有节点向周围扩散 */
for (String cur : q1) {
if(deads.contains(cur)) {
continue;
}
//这里判断双队列是否有交集，如果有交集，则找到最短路径
if(q2.contains(cur)) {
return dep;
}
visited.add(cur);
/* 将一个节点的未遍历相邻节点加入集合 */
for(int j=0;j<4;j++) {
String up = plusOne(cur,j);
if(!visited.contains(up)) {
temp.add(up);
}
String down = minusOne(cur,j);
if(!visited.contains(down)) {
temp.add(down);
}
}
}
//交换q1和q2
// temp 相当于 q1
// 这里交换 q1 q2，下一轮 while 就是扩散 q2
q1=q2;
q2=temp;
dep++;
}
return -1;
}
String plusOne(String s,int j) {
//往上波动
char[] ch = s.toCharArray();
if(ch[j] == '9') {
ch[j] ='0';
}else {
ch[j] +=1;
}
return new String(ch);
}
String minusOne(String s,int j) {
//向下波动
char[] ch = s.toCharArray();
if(ch[j] == '0') {
ch[j] = '9';
}else {
ch[j]-=1;
}
return new String(ch);
}
}
2.二叉树的最小深度
题目描述
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
代码题解：
class Solution {
public int minDepth(TreeNode root) {
if(root ==null) {
return 0;
}
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int dep =1;
while(!q.isEmpty()) {
int size = q.size();
/* 将当前队列中的所有节点向四周扩散 */
for(int i = 0;i<size;i++) {
TreeNode t = q.poll();
if(t.left==null&&t.right==null) {
return dep;
}
/* 将 t 的相邻节点加入队列 */
if(t.left!=null) {
q.offer(t.left);
}
if(t.right!=null) {
q.offer(t.right);
}
}
dep++;
}
return dep;
}
}