BFS 广度优先搜索的本质是一幅「图」从一个 start 起点走到 target 终点，问最短路径
BFS 可以找到最短距离，但是空间复杂度高，而 DFS 的空间复杂度较低
BFS、DFS 模板
for len(queue) > 0 {
for i, node := range queue {
queue.push(未访问过的结点)
}
queue = queue[len(queue):]
}
dfs = func(node *TreeNode) {
if node == nil { return } // 递归终止条件
// 前序遍历 操作数据
dfs(node.Left)
dfs(node.Right)
}
// 计算从 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++;
}
}
111. Minimum Depth of Binary Tree
int minDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int depth = 1; // root 本身即一层，depth 初始化为 1
while (!q.isEmpty()) {
int sz = q.size();
/* 将当前队列中所有结点向四周扩散 */
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
/* 判断是否到终点 */
if (cur.left == null && cur.right == null)
return depth;
/* 将 cur 相邻结点加入队列 */
if (cur.left != null)
q.offer(cur.left);
if (cur.right != null)
q.offer(cur.right);
}
depth++; // 增加步数
}
return depth;
}
注意两个循环的配合，外层 while 控制一层层往下走，内层 for 循环利用 sz 控制从左到右遍历每一层二叉树结点（遍历过程中队列 q 控制出列
752. Open the Lock
带四个圆形拨轮的转盘锁，穷举其密码组合，每个位置可以向上或向下，即一共八种可能，如从 "0000" 开始，转一次可以有 "1000", "9000", "0100", "0900"... 8 种密码，可以抽象成一幅图，图中每个结点有 8 个相邻结点，求最短距离
int openLock(String[] deadends, String target) {
// 记录需要跳过的死亡密码
Set<String> deads = new HashSet<>();
for (String s : deadends) deads.add(s);
// 记录已经穷举过的密码，防止走回头路
Set<String> visited = new HashSet<>();
Queue<String> q = new LinkedList<>();
// 从起点开始启动广度优先搜索
int step = 0;
q.offer("0000");
visited.add("0000");
while (!q.isEmpty()) {
int sz = q.size();
/* 将当前队列中的所有节点向周围扩散 */
for (int i = 0; i < sz; i++) {
String cur = q.poll();
/* 判断是否到达终点 */
if (deads.contains(cur))
continue;
if (cur.equals(target))
return step;
/* 将一个节点的未遍历相邻节点加入队列 */
for (int j = 0; j < 4; j++) {
String up = plusOne(cur, j);
if (!visited.contains(up)) {
q.offer(up);
visited.add(up);
}
String down = minusOne(cur, j);
if (!visited.contains(down)) {
q.offer(down);
visited.add(down);
}
}
}
/* 在这里增加步数 */
step++;
}
// 如果穷举完都没找到目标密码，那就是找不到了
return -1;
}
func openLock(deadends []string, target string) int {
if target == "0000" {
return 0
}
visited := map[string]bool{"0000": true}
for _, s := range deadends {
visited[s] = true
}
step := 0
q := []string{"0000"}
for len(q) > 0 {
sz := len(q)
for i := 0; i < sz; i++ {
cur := q[0]
q = q[1:]
if cur == target {
return step
}
// 将一个结点的未遍历相邻结点加入队列
for j := 0; j < 4; j++ {
up := plusOne(cur, j)
if !visited[up] {
q = append(q, up)
visited[up] = true
}
down := minusOne(cur, j)
if !visited[down] {
q = append(q, down)
visited[down] = true
}
}
}
step++
}
return -1
}
// 将 s[j] 向上拨动一次
func plusOne(s string, j int) string {
chars := []rune(s) // '0000' -> [48, 48, 48, 48]
if chars[j] == '9' {
chars[j] = '0'
} else {
chars[j] += 1
}
return string(chars)
}
// 向下拨动一次
func minusOne(s string, j int) string {
chars := []rune(s)
if chars[j] == '0' {
chars[j] = '9'
} else {
chars[j] -= 1
}
return string(chars)
}
单向 BFS 框架从起点开始向四周扩散，遇到终点时停止；双向 BFS 从起点和终点同时开始扩散，当两边有交集的时候停止
int openLock(String[] deadends, String target) {
Set<String> deads = new HashSet<>();
for (String s : deadends) deads.add(s);
// 用集合不用队列，可以快速判断元素是否存在
Set<String> q1 = new HashSet<>();
Set<String> q2 = new HashSet<>();
Set<String> visited = new HashSet<>();
int step = 0;
q1.add("0000");
q2.add(target);
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 step;
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);
}
}
/* 在这里增加步数 */
step++;
// temp 相当于 q1
// 这里交换 q1 q2，下一轮 while 就是扩散 q2
q1 = q2;
q2 = temp;
}
return -1;
}
双向 BFS 不再使用队列，而用 HashSet 快速判断两个集合是否有交集