图的 BFS：多源BFS与最短路

单词接龙（LeetCode 127）

最短转换序列长度（BFS 层序遍历、双向BFS）：

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> wordSet = new HashSet<>(wordList);
    if (!wordSet.contains(endWord)) return 0;
    Queue<String> queue = new ArrayDeque<>();
    queue.offer(beginWord);
    int steps = 1;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String word = queue.poll();
            char[] chars = word.toCharArray();
            for (int j = 0; j < chars.length; j++) {
                char original = chars[j];
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == original) continue;
                    chars[j] = c;
                    String next = new String(chars);
                    if (next.equals(endWord)) return steps + 1;
                    if (wordSet.remove(next)) queue.offer(next);  // 访问后移除，避免重复
                }
                chars[j] = original;
            }
        }
        steps++;
    }
    return 0;
}

双向 BFS 优化（从两端同时扩展，减少搜索空间）：

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> wordSet = new HashSet<>(wordList);
    if (!wordSet.contains(endWord)) return 0;
    Set<String> beginSet = new HashSet<>(), endSet = new HashSet<>();
    beginSet.add(beginWord); endSet.add(endWord);
    int steps = 1;
    while (!beginSet.isEmpty()) {
        // 每次从较小的一端扩展
        if (beginSet.size() > endSet.size()) { Set<String> tmp = beginSet; beginSet = endSet; endSet = tmp; }
        Set<String> nextSet = new HashSet<>();
        for (String word : beginSet) {
            char[] chars = word.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char orig = chars[i];
                for (char c = 'a'; c <= 'z'; c++) {
                    chars[i] = c;
                    String next = new String(chars);
                    if (endSet.contains(next)) return steps + 1;
                    if (wordSet.remove(next)) nextSet.add(next);
                }
                chars[i] = orig;
            }
        }
        beginSet = nextSet;
        steps++;
    }
    return 0;
}

打开转盘锁（LeetCode 752）

从 "0000" 转到目标，每步拨一个数字±1，避开死亡组合，求最少步骤：

public int openLock(String[] deadends, String target) {
    Set<String> dead = new HashSet<>(Arrays.asList(deadends));
    if (dead.contains("0000")) return -1;
    Queue<String> queue = new ArrayDeque<>();
    Set<String> visited = new HashSet<>();
    queue.offer("0000"); visited.add("0000");
    int steps = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String cur = queue.poll();
            if (cur.equals(target)) return steps;
            for (int j = 0; j < 4; j++) {
                for (int d : new int[]{1, -1}) {
                    char[] next = cur.toCharArray();
                    next[j] = (char)(((next[j] - '0' + d + 10) % 10) + '0');
                    String ns = new String(next);
                    if (!visited.contains(ns) && !dead.contains(ns)) {
                        visited.add(ns); queue.offer(ns);
                    }
                }
            }
        }
        steps++;
    }
    return -1;
}

腐烂的橘子（LeetCode 994）

多源 BFS，所有腐烂橘子同时向外扩散，统计最短时间：

public int orangesRotting(int[][] grid) {
    Queue<int[]> queue = new ArrayDeque<>();
    int fresh = 0, m = grid.length, n = grid[0].length;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2) queue.offer(new int[]{i, j});
            else if (grid[i][j] == 1) fresh++;
        }
    int time = 0;
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    while (!queue.isEmpty() && fresh > 0) {
        time++;
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                int r = cell[0] + d[0], c = cell[1] + d[1];
                if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) {
                    grid[r][c] = 2; fresh--; queue.offer(new int[]{r, c});
                }
            }
        }
    }
    return fresh == 0 ? time : -1;
}

总结