思路

应用场景：最短路径。对比DFS，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++;
    }
}

还有一种双向bfs优化，知道起点和

例题

111. 二叉树的最小深度

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int depth = 1;
        while (!queue.isEmpty()) {
            // 这一层节点数量
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null) return depth;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            depth++;
        }
        return depth;
    }
}

752. 打开转盘锁

转动一次4位转盘一共有八种方式，所以每个状态节点相邻有八个状态节点，这样就能将问题转化成广度搜索问题。搜到的第一个符合要求的状态时的步数就是答案。
deads和visited的作用实际上一样，也可以一开始就将deadends里面的状态加入visited中，效果相同，都是遇到了就不理睬它的相邻状态节点就好了。

class Solution {
    public int openLock(String[] deadends, String target) {
        // bfs辅助队列
        Queue<String> queue = new LinkedList<>();
        queue.offer("0000");
        // 死亡情况set
        Set<String> deads = new HashSet<>();
        for (String deadend : deadends) deads.add(deadend);
        // 记录走过的路
        Set<String> visited = new HashSet<>();
        visited.add("0000");
        // 从起点开始步骤数
        int stepNum = 0;
        while (!queue.isEmpty()) {
            int sz = queue.size();
            // 向节点周围扩散
            for (int i = 0; i < sz; ++i) {
                String cur = queue.poll();
                // 判断dead和target，遇到dead就不能继续走了，遇到target就直接返回当前步数
                if (deads.contains(cur)) continue;
                if (cur.equals(target)) return stepNum;
                // 周围节点（八个）加入队列（四个wheels分别 + - ）
                for (int j = 0; j < 4; ++j) {
                    String up = plusOne(cur, j);
                    // 访问过的状态就不考虑了，避免死循环
                    if (!visited.contains(up)) {
                        queue.offer(up);
                        visited.add(up);
                    }
                    String down = minusOne(cur, j);
                    if (!visited.contains(down)) {
                        queue.offer(down);
                        visited.add(down);
                    }
                }
            }
            ++stepNum;
        }
        // 无法实现
        return -1;
    }
    // No.i wheel +1
    private String plusOne(String lock, int i) {
        char[] arr = lock.toCharArray();
        if (arr[i] == '9') arr[i] = '0';
        else arr[i]++;
        return new String(arr);
    }
    // No.i wheel -1
    private String minusOne(String lock, int i) {
        char[] arr = lock.toCharArray();
        if (arr[i] == '0') arr[i] = '9';
        else arr[i]--;
        return new String(arr);
    }
}