知识文档站

Appearance

bfs 及其扩展

bfs 基本介绍 ​

bfs 的特点是逐层扩散，从源头点到目标点扩散了几层，最短路就是多少 ​

bfs 可以使用的特征是任意两个节点之间的相互距离相同（无向图） ​

bfs 开始时，可以是单个源头、也可以是多个源头 ​

bfs 频繁使用队列，形式可以是单点弹出或者整层弹出 ​

bfs 进行时，进入队列的节点需要标记状态，防止同一个节点重复进出队列 ​

bfs 进行时，可能会包含剪枝策略的设计 ​

bfs 是一个理解难度很低的算法，难点在于节点如何找到路、路的展开和剪枝设计 ​

地图分析 ​

题目链接 ​

https://leetcode.cn/problems/as-far-from-land-as-possible/ ​

思路分析 ​

本题的曼哈顿距离意思就是水平方向和竖直方向的距离之和，即通过 bfs 搜索四个方向，走几步能到，通过 bfs 层标记记录距离，认为初始为 1，又因为海洋为 0，则答案为最终的标记值 - 1 即为最大距离 ​

代码实现 ​

java
class Solution {

    public static int MAXN = 101;

    public static int MAXM = 101;

    public static int[][] queue = new int[MAXN * MAXM][2];

    public static int l, r;

    public static boolean[][] visited = new boolean[MAXN][MAXM];

    // 0:上，1:右，2:下，3:左
    public static int[] dirs = new int[] { -1, 0, 1, 0, -1 };
    //                                      0  1  2  3   4
    //                                               i
    // (x,y)  i来到0位置 : x + dirs[i], y + dirs[i+1] -> x - 1, y
    // (x,y)  i来到1位置 : x + dirs[i], y + dirs[i+1] -> x, y + 1
    // (x,y)  i来到2位置 : x + dirs[i], y + dirs[i+1] -> x + 1, y
    // (x,y)  i来到3位置 : x + dirs[i], y + dirs[i+1] -> x, y - 1

    public int maxDistance(int[][] grid) {
        // 清空脏数据
        l = r = 0;
        int n = grid.length;
        int m = grid[0].length;
        int seas = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    visited[i][j] = true;
                    queue[r][0] = i;
                    queue[r++][1] = j;
                } else {
                    visited[i][j] = false;
                    seas++;
                }
            }
        }
        // 题目要求：只有陆地或者海洋
        if (seas == 0 || seas == n * m) {
            return -1;
        }
        int level = 0;
        // bfs 处理每一层，通过层标记来记录距离
        while (l < r) {
            level++;
            int size = r - l;
            for (int k = 0; k < size; k++) {
                int x = queue[l][0];
                int y = queue[l++][1];
                for (int i = 0; i < 4; i++) {
                    // 遍历上下左右四个方向
                    int nextX = x + dirs[i];
                    int nextY = y + dirs[i + 1];
                    if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && !visited[nextX][nextY]) {
                        visited[nextX][nextY] = true;
                        queue[r][0] = nextX;
                        queue[r++][1] = nextY;
                    }
                }
            }
        }
        return level - 1;
    }
}

贴纸拼词 ​

题目链接 ​

https://leetcode.cn/problems/stickers-to-spell-word/ ​

思路分析 ​

对字符串排序，优先搞定前缀实现剪枝策略，避免不必要的展开，每一张贴纸看能搞定多少个字符，下一层的结果就是贴纸搞定做少个字符后得到的剩余字符串，依次向下展开，直到搞定所有的字符，直到遇到空字符串，展开的层数就是需要的贴纸个数 ​

代码实现 ​

java
class Solution {
    public static int MAXN = 401;

    public static String[] queue = new String[MAXN];

    public static int l, r;

    // 下标0 -> a
    // 下标1 -> b
    // 下标2 -> c
    // ...
    // 下标25 -> z
    // 每个下标对应的链表存储能搞定该下标对应字符的贴纸
    public static List<List<String>> graph = new ArrayList<>();

    // 初始化邻接表
    static {
        for (int i = 0; i < 26; i++) {
            graph.add(new ArrayList<>());
        }
    }

    public static HashSet<String> visited = new HashSet<>();

    // 宽度优先遍历的解法
    // 也可以使用动态规划
    // 后续课程会有动态规划专题讲解
    public int minStickers(String[] stickers, String target) {
        for (int i = 0; i < 26; i++) {
            graph.get(i).clear();
        }
        visited.clear();
        for (String str : stickers) {
            str = sort(str);
            for (int i = 0; i < str.length(); i++) {
                // 是首字符或者是不相同的字符的才记录贴纸
                if (i == 0 || str.charAt(i) != str.charAt(i - 1)) {
                    graph.get(str.charAt(i) - 'a').add(str);
                }
            }
        }
        target = sort(target);
        visited.add(target);
        l = r = 0;
        queue[r++] = target;
        int level = 1;
        // bfs 处理整层
        while (l < r) {
            int size = r - l;
            for (int i = 0; i < size; i++) {
                String cur = queue[l++];
                // 遍历包含首字符的贴纸
                for (String s : graph.get(cur.charAt(0) - 'a')) {
                    String next = next(cur, s);
                    if (next.equals("")) {
                        return level;
                    } else if (!visited.contains(next)) {
                        visited.add(next);
                        queue[r++] = next;
                    }
                }
            }
            level++;
        }
        return -1;
    }

    public static String sort(String str) {
        char[] s = str.toCharArray();
        Arrays.sort(s);
        return String.valueOf(s);
    }

    // 双指针遍历，实现字符匹配，进而得到展开后的字符串
    public static String next(String t, String s) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0, j = 0; i < t.length(); ) {
            if (j == s.length()) {
                builder.append(t.charAt(i++));
            } else {
                if (t.charAt(i) < s.charAt(j)) {
                    builder.append(t.charAt(i++));
                } else if (t.charAt(i) > s.charAt(j)) {
                    j++;
                } else {
                    // 相等说明可以被搞定，指针后移
                    i++;
                    j++;
                }
            }
        }
        return builder.toString();
    }
}

01 bfs 基本介绍 ​

01bfs，适用于图中所有边的权重只有0和1两种值 ​

求源点到目标点的最短距离时间复杂度：O（节点数量 + 边的数量） ​

1. distance [ i ] 表示从源点到点i的最短距离，初始时所有点的distance设置为无穷大 ​

2，源点进入双端队列，distance [ 源点 ] = 0 ​

3，双端队列头部弹出 x ​

A：如果 x 是目标点，返回 distance [ x ] 表示源点到目标点的最短距离 ​

B：考察从 x 出发的每一条边，假设某边去 v 点，边权为 w ​

（1）如果 distance [ y ] > distance [ x ] + w，处理该边，否则忽略该边 ​

（2）处理时，更新 distance [ y ] = distance [ x ] + w ​

如果 w==0 ，y 从头部进入双端队列，如果 w==1 ，y 从尾部进入双端队列 ​

（3）考察完 x 出发的所有边之后，重复步骤 3 ​

4，双端队列为空停止 ​

⚠️ 提示

正确性证明以及为什么不需要 visited 来标记节点见视频讲解 ​

到达角落的最小移除代价 ​

题目链接 ​

https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner/ ​

思路分析 ​

01 bfs 模板题，具体思路见 01 bfs 基本介绍，结合代码理解 ​

代码实现 ​

java
class Solution {
    public int minimumObstacles(int[][] grid) {
        int[] move = { -1, 0, 1, 0, -1 };
        // n 行 m 列
        int n = grid.length;
        int m = grid[0].length;
        int[][] distance = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                distance[i][j] = Integer.MAX_VALUE;
            }
        }
        // 双端队列
        Deque<int[]> deque = new ArrayDeque<>();
        deque.addFirst(new int[] { 0, 0 });
        distance[0][0] = 0;
        while (!deque.isEmpty()) {
            int[] record = deque.pollFirst();
            int x = record[0];
            int y = record[1];
            if (x == n - 1 && y == m - 1) {
                return distance[x][y];
            }
            for (int i = 0; i < 4; i++) {
                int nextX = x + move[i];
                int nextY = y + move[i + 1];
                if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m &&
                        distance[x][y] + grid[nextX][nextY] < distance[nextX][nextY]) {
                    distance[nextX][nextY] = distance[x][y] + grid[nextX][nextY];
                    // w = 0 从头进，w = 1 从尾进
                    if (grid[nextX][nextY] == 0) {
                        deque.addFirst(new int[] { nextX, nextY });
                    } else {
                        deque.addLast(new int[] { nextX, nextY });
                    }
                }
            }
        }
        return -1;
    }
}

至少有一条有效路径的最小代价 ​

题目链接 ​

https://leetcode.cn/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/ ​

思路分析 ​

本题做一个转化，每个格子有 4 条边，认为箭头所指方向的边为 0，其余边为 1，那整个图就相当于是一个 01 图，问从左上角到右下角改几次箭头就相当于从左上角到右下角走了多少个权值为 1 的边，且要求距离最短 ​

代码实现 ​

java
class Solution {
    public int minCost(int[][] grid) {
        // 格子的数值 :
        // 1 右
        // 2 左
        // 3 下
        // 4 上
        //               0     1       2       3        4
        int[][] move = { {}, { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
        // n 行 m 列
        int n = grid.length;
        int m = grid[0].length;
        int[][] distance = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                distance[i][j] = Integer.MAX_VALUE;
            }
        }
        Deque<int[]> deque = new ArrayDeque<>();
        deque.addFirst(new int[] { 0, 0 });
        distance[0][0] = 0;
        while (!deque.isEmpty()) {
            int[] record = deque.pollFirst();
            int x = record[0];
            int y = record[1];
            if (x == n - 1 && y == m - 1) {
                return distance[x][y];
            }
            for (int i = 1; i <= 4; i++) {
                int nextX = x + move[i][0];
                int nextY = y + move[i][1];
                // 如果遍历方向和箭头方向不一致，则认为是 1，否则为 0
                int weight = grid[x][y] != i ? 1 : 0;
                if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m &&
                        distance[x][y] + weight < distance[nextX][nextY]) {
                    distance[nextX][nextY] = distance[x][y] + weight;
                    if (weight == 0) {
                        deque.addFirst(new int[] { nextX, nextY });
                    } else {
                        deque.addLast(new int[] { nextX, nextY });
                    }
                }
            }
        }
        return -1;
    }
}

二维接雨水 ​

题目链接 ​

https://leetcode.cn/problems/trapping-rain-water-ii/ ​

思路分析 ​

将题中的图抽象为一个二维矩阵，采用 bfs 搜索，每个数据存储结构为：行、列、水线，结合小根堆，按照水线排序从小到大排序，水线值小的维持在堆顶，bfs 过程中水线取最大值后存入小根堆，在弹出时结算容纳水的量 ​

代码实现 ​

java
class Solution {
    public int trapRainWater(int[][] heightMap) {
        int[] move = { -1, 0, 1, 0, -1 };
        // n 行 m 列
        int n = heightMap.length;
        int m = heightMap[0].length;
        // 0 ：行，1 ：列，2 ：水线
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> (a[2] - b[2]));
        boolean[][] visited = new boolean[n][m];
        // 开始时初始化边界，能否接住雨水依赖于边界
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                    // 边界
                    heap.add(new int[] { i, j, heightMap[i][j] });
                    visited[i][j] = true;
                } else {
                    visited[i][j] = false;
                }
            }
        }
        int ans = 0;
        while (!heap.isEmpty()) {
            int[] record = heap.poll();
            int x = record[0];
            int y = record[1];
            int weight = record[2];
            ans += weight - heightMap[x][y];
            for (int i = 0; i < 4; i++) {
                int nextX = x + move[i];
                int nextY = y + move[i + 1];
                if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && !visited[nextX][nextY]) {
                    heap.add(new int[] { nextX, nextY, Math.max(weight, heightMap[nextX][nextY]) });
                    visited[nextX][nextY] = true;
                }
            }
        }
        return ans;
    }
}

单词接龙 II ​

题目链接 ​

https://leetcode.cn/problems/word-ladder-ii/ ​

思路分析 ​

遍历单词的每个字符，将该字符用 26 个字母替换，判断替换后生成的单词是否在单词列表中，依次搜索，最后通过 dfs 生成路径返回 ​

代码实现 ​

java
class Solution {
    // 单词表：list -> hashset
    public static HashSet<String> dict;

    public static HashSet<String> curLevel = new HashSet<>();

    public static HashSet<String> nextLevel = new HashSet<>();

    // 反向图，用于 dfs 构建路径
    public static HashMap<String, ArrayList<String>> graph = new HashMap<>();

    // 记录路径，生成有效路径并记录结果
    public static LinkedList<String> path = new LinkedList<>();

    public static List<List<String>> ans = new ArrayList<>();

    public static void build(List<String> wordList) {
        dict = new HashSet<>(wordList);
        graph.clear();
        ans.clear();
        curLevel.clear();
        nextLevel.clear();
    }

    public static List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        build(wordList);
        if (!dict.contains(endWord)) {
            return ans;
        }
        if (bfs(beginWord, endWord)) {
            dfs(endWord, beginWord);
        }
        return ans;
    }

    // begin -> end，一层层 bfs 建图
    // 返回值：真的能找到 end 返回 true，否则返回 false
    public static boolean bfs(String begin, String end) {
        boolean find = false;
        curLevel.add(begin);
        while (!curLevel.isEmpty()) {
            // 去除已经出现过的，确保不同层的单词都是不一样的，而不出现重复
            dict.removeAll(curLevel);
            for (String word : curLevel) {
                // 每个位置用 a - z 替换，并检查在词表中是否存在，避免加工出自己
                char[] w = word.toCharArray();
                for (int i = 0; i < w.length; i++) {
                    char old = w[i];
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        w[i] = ch;
                        String str = String.valueOf(w);
                        if (dict.contains(str) && !str.equals(word)) {
                            if (str.equals(end)) {
                                find = true;
                            }
                            // 没有就建，有就复用原来的
                            graph.putIfAbsent(str, new ArrayList<>());
                            // 构建反向图，记录哪些 word 可以变成 str，便于后续 dfs 构建路径
                            graph.get(str).add(word);
                            // str 作为替换后的结果，加入到下一层的结果集中
                            nextLevel.add(str);
                        }
                    }
                    // 一个位置的字符跑完，恢复原来的字符，继续跑下一个字符
                    w[i] = old;
                }
            }
            if (find) {
                return true;
            } else {
                // 继续下一层 bfs 搜索
                HashSet<String> tmp = curLevel;
                curLevel = nextLevel;
                nextLevel = tmp;
                nextLevel.clear();
            }
        }
        return false;
    }

    public static void dfs(String word, String aim) {
        path.addFirst(word);
        if (word.equals(aim)) {
            ans.add(new ArrayList<>(path));
        } else if (graph.containsKey(word)) {
            for (String next : graph.get(word)) {
                dfs(next, aim);
            }
        }
        path.removeFirst();
    }
}

Copyright © 2025 Jackson 凌 All Rights Reserved. | 粤ICP备2025441629号-1