跳到主要内容
极客日志极客日志面向AI+效率的开发者社区
首页博客GitHub 精选镜像AI 生图工具UI配色美学隐私政策关于联系
搜索内容 / 工具 / 仓库 / 镜像...⌘K搜索
注册
博客列表
Javajava算法

多源 BFS 算法原理及经典题目解析

多源广度优先搜索用于解决多个起点到终点的最短路径问题。通过将多个起点同时加入队列，利用层序遍历计算距离。文章涵盖四个经典 LeetCode 题目：01 矩阵计算每个元素到最近 0 的距离；飞地的数量统计不与边界相连的 1 的数量；地图中的最高点将水域设为 0 向外扩展高度；地图分析寻找离陆地最远的水域距离。核心思路是将所有符合条件的初始点入队，统一进行 BFS 扩展，避免重复计算，时间复杂度优化至 O(M*N)。

禅心发布于 2026/3/26更新于 2026/7/2535 浏览
多源 BFS 算法原理及经典题目解析

一、多源 BFS

单源最短路：只有一个起点到终点的最短路问题。 多源最短路问题：有多个起点到终点的最短路问题。 多源 BFS：用 BFS 来解决边权相同的多源最短路问题。

解法：

  1. 暴力解题，把多源最短路问题，转化为若干个单源最短路问题。
  2. 把所有起点当成一个起点，问题就变成了单源最短路问题。

二、542.01 矩阵

题目链接：542.01 矩阵

题目描述：

文章配图

题目解析：

  • 给一个只有 0 1 的二维数组，计算其中每一个元素到 0 的最短距离，自己是 0 距离就是 0，将距离存入一个相同规模二维数组的下标中。

方法一

解题思路：

  • 我们如果遍历数组，找到 1 后，就进行求该元素到 0 的最短距离。
  • 求最短距离就使用前面求权值相同的最短距离的方法即可。
  • 但是会超时。
//时间复杂度：O(M*N*M*N)//空间复杂度：O(M*N)
class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int m, n;

    public int[][] updateMatrix(int[][] mat) {
        m = mat.length;
        n = mat[0].length;
        int[][] ret = new int[m][n];
        // 遍历 mat，遍历到 1 找最近的 0
        for (int i = 0; i < m; i++) {
            for (int j  ; j < n; j++) {
                 ( == mat[i][j]) {
                    ret[i][j] = ;
                }  {
                    ret[i][j] = bfs(mat, i, j);
                }
            }
        }
         ret;
    }

       {
        Queue<[]> queue =  <>();
        queue.add( []{x, y});
        [][] flag =  [m][n];
        flag[x][y] = ;
           ;
         (!queue.isEmpty()) {
            ret++;
               queue.size();
             (size-- != ) {
                [] arr = queue.poll();
                 (   ; i < ; i++) {
                       arr[] + dx[i];
                       arr[] + dy[i];
                    
                     (a >=  && a < m && b >=  && b < n && !flag[a][b] && mat[a][b] != ) {
                        flag[a][b] = ;
                        queue.add( []{a, b});
                    }
                    
                     (a >=  && a < m && b >=  && b < n && mat[a][b] == )  ret;
                }
            }
        }
         ;
    }
}
=
0
if
0
0
else
return
public
int
bfs
(int[][] mat, int x, int y)
int
new
LinkedList
new
int
boolean
new
boolean
true
int
ret
=
0
while
int
size
=
while
0
int
for
int
i
=
0
4
int
a
=
0
int
b
=
1
// 入队
if
0
0
0
true
new
int
// 结束条件
if
0
0
0
return
return
0

方法二

解题思路：

  • 我们先将数组中的所有 0 下标，记录下来放入队列中。
  • 然后我们层序遍历，每一次循环遍历完当前队列中的值，往外 BFS 寻找没被标记的 1，寻找的循环次数就是这个 1 的最短距离。
//时间复杂度：O(M*N)//空间复杂度：O(M*N)
class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};

    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] ret = new int[m][n];
        boolean[][] flag = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        // 遍历 mat，先把 0 全部放入队列
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (0 == mat[i][j]) {
                    queue.add(new int[]{i, j});
                    ret[i][j] = 0;
                }
            }
        }
        // 遍历队列中的元素，层序递进
        int tep = 0;
        while (!queue.isEmpty()) {
            tep++;
            int size = queue.size();
            while (size-- != 0) {
                int[] arr = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int x = arr[0] + dx[i];
                    int y = arr[1] + dy[i];
                    // 入队
                    if (x >= 0 && x < m && y >= 0 && y < n && 1 == mat[x][y] && !flag[x][y]) {
                        flag[x][y] = true;
                        queue.add(new int[]{x, y});
                        ret[x][y] = tep;
                    }
                }
            }
        }
        return ret;
    }
}

改进

  • 我们就可以直接使用结果数组，来达到上面的 flag 数组的记录功能，也不再需要记录层数。
  • 我们将 mat 数组中元素为 1 对应的 ret 结果数组元素记录为 -1；
  • 当我们 BFS 的时候，如果 ret 元素为 -1，那么证明没有记录过，那么这个元素值就是出队列元素对应的 ret 值加一；
  • 当 ret 中数组元素没有 -1 了就会结束。
//时间复杂度：O(M*N)//空间复杂度：O(M*N)
class Solution {
    int[] dx = new int[]{0, 0, 1, -1};
    int[] dy = new int[]{1, -1, 0, 0};

    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] ret = new int[m][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ret[i][j] = -1;
                if (mat[i][j] == 0) {
                    queue.add(new int[]{i, j});
                    ret[i][j] = 0;
                }
            }
        }
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x = arr[0] + dx[i];
                int y = arr[1] + dy[i];
                // 入队
                if (x >= 0 && x < m && y >= 0 && y < n && ret[x][y] == -1) {
                    queue.add(new int[]{x, y});
                    ret[x][y] = ret[arr[0]][arr[1]] + 1;
                }
            }
        }
        return ret;
    }
}

三、1020.飞地的数量

题目链接：1020.飞地的数量

题目描述：

文章配图

题目解析：

  • 给我们一个只有 0 1 的数组，让我们统计（上下左右）连成块的 1，并且这其中 1 没有在数组边的个数。

解题思路：

  • 我们使用标记数组标记 0 和处于边上的 1
  • 将边上 1 的坐标放入队列
  • 在对队列中的元素实行 BFS，入队条件是没被标记的元素。
  • 执行完 BFS，就只会有符合条件的 1 没有被标记。
  • 我们使用数组元素个数作为返回值，标记一次返回值就减 1，最后就是所求值。
//时间复杂度：O(M*N)//空间复杂度：O(M*N)
class Solution {
    int[] dx = new int[]{0, 0, 1, -1};
    int[] dy = new int[]{1, -1, 0, 0};

    public int numEnclaves(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] flag = new boolean[m][n];
        // 先将所有边界 1 入队并标记，将 0 标记
        int ret = m * n;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && (i == 0 || i == m - 1 || j == 0 || j == n - 1)) {
                    queue.add(new int[]{i, j});
                    flag[i][j] = true;
                    ret--;
                } else if (grid[i][j] == 0) {
                    flag[i][j] = true;
                    ret--;
                }
            }
        }
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x = arr[0] + dx[i];
                int y = arr[1] + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && !flag[x][y]) {
                    ret--;
                    queue.add(new int[]{x, y});
                    flag[x][y] = true;
                }
            }
        }
        return ret;
    }
}

四、1765.地图中的最高点

题目链接：1765. 地图中的最高点

题目描述：

文章配图

题目解析：

  • 给我们一个数组，其中 1 代表水域，0 代表陆地。
  • 要求返回一个 height 高度数组，数组元素比上下左右元素高度差不超过一。返回能使 height 元素达到最大值的结果。

解题思路：

  • 我们先将水域入队，然后从水域元素往外扩，将四周元素入队，并且使其 height 值比让他入队的元素大 1
  • 每个元素只能入一次对列，我们要有标技数组，我们可以直接使用 height 为标记数组，初始化时将陆地元素赋值 -1，只要是值不是 -1 的元素就证明入过对列了。
//时间复杂度：O(M*N)//空间复杂度：O(M*N)
class Solution {
    int[] dx = new int[]{0, 0, 1, -1};
    int[] dy = new int[]{1, -1, 0, 0};

    public int[][] highestPeak(int[][] isWater) {
        int m = isWater.length;
        int n = isWater[0].length;
        int[][] height = new int[m][n];
        Queue<int[]> queue = new LinkedList<>();
        // 遍历 isWater 数组，1 水域对应 height 为 0，并入对，其余为 -1，起标记作用
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                height[i][j] = -1;
                if (isWater[i][j] == 1) {
                    height[i][j] = 0;
                    queue.add(new int[]{i, j});
                }
            }
        }
        // BFS
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x = arr[0] + dx[i];
                int y = arr[1] + dy[i];
                // height 为 -1 入队，值为出队列元素加 1
                if (x >= 0 && x < m && y >= 0 && y < n && height[x][y] == -1) {
                    height[x][y] = height[arr[0]][arr[1]] + 1;
                    queue.add(new int[]{x, y});
                }
            }
        }
        return height;
    }
}

五、1162.地图分析

题目链接：1162. 地图分析

题目描述：

文章配图

题目解析：

  • 给我们一个 grid 数组，只有 0 1
  • 找出 0 通过上下左右走到最近的 1 的距离的最大值

解题思路：

  • 一个最经典的多源 BFS
  • 我们从 1 开始走（将 1 全部入队），每走一次（将当前队列元素出完，将元素上下左右的没标记过的 0 入队），直到走完所有元素，最后走的次数就是结果。
//时间复杂度：O(M*N)//空间复杂度：O(M*N)
class Solution {
    int[] dx = new int[]{0, 0, 1, -1};
    int[] dy = new int[]{1, -1, 0, 0};

    public int maxDistance(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int ret = 0;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] flag = new boolean[m][n];
        // 所有 1 入队
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue.add(new int[]{i, j});
                    flag[i][j] = true;
                    ret++;
                }
            }
        }
        // 判断是否全 0 或全 1
        if (ret == 0 || ret == m * n) return -1;
        ret = -1;
        // BFS
        while (!queue.isEmpty()) {
            int size = queue.size();
            ret++;
            while (size-- != 0) {
                int[] arr = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int x = arr[0] + dx[i];
                    int y = arr[1] + dy[i];
                    // 入队
                    if (x >= 0 && x < m && y >= 0 && y < n && !flag[x][y] && grid[x][y] == 0) {
                        queue.add(new int[]{x, y});
                        flag[x][y] = true;
                    }
                }
            }
        }
        return ret;
    }
}

目录

  1. 一、多源 BFS
  2. 二、542.01 矩阵
  3. 方法一
  4. 方法二
  5. 改进
  6. 三、1020.飞地的数量
  7. 四、1765.地图中的最高点
  8. 五、1162.地图分析
  • 免费图片AI生成工具免费生成了解详情
  • Magick API 一键接入全球大模型注册送1000万token查看
  • 免费图片视频在线生成30秒，将你的创意变成现实开始设计
  • X/Twitter免费视频下载器免登陆无限额度免费视频解析下载了解详情
  • 100+免费在线小游戏爽一把
极客日志微信公众号二维码

微信扫一扫，关注极客日志

微信公众号「极客日志V2」，在微信中扫描左侧二维码关注。展示文案：极客日志V2 zeeklog

更多推荐文章

查看全部
  • SmolVLA 高算力适配：TensorRT 加速可行性分析与 ONNX 导出实操
  • MySQL 数据库基础入门：从概念到实战
  • Gazebo 机器人三维物理仿真平台详解
  • 清华大学与智谱团队探索 RLHF 的 Scaling Laws
  • Stable Diffusion v1.5 故障艺术与赛博朋克融合生成指南
  • 多模态模型开发实战：文本、图像与语音融合应用
  • 基于 LangChain 与 Gradio 搭建个人知识助手
  • IntelliJ IDEA 打包 Web 项目 WAR 包（含 Tomcat 部署+常见问题解决）
  • Android 陀螺仪基础：传感器数据与角度积分计算
  • VSCode AI Copilot 智能补全失效修复指南
  • Flutter 组件 Spry 适配鸿蒙实战：轻量级端侧 Web 服务构建
  • 利用闲置 Mac Mini 部署 OpenClaw 构建本地金融 AI 助手
  • 垂直领域大模型构建：RAG 与微调的权衡与实践
  • 无人机基本组成与结构设计
  • 基于 AI 的智能算力分配与云原生基础设施实践
  • Vitis 部署 AI 模型到 FPGA 实战指南
  • Midjourney 以图生图与提示词反推教程
  • DiT（Diffusion Transformer）详解：架构与核心模块分析
  • Spring Boot 实现后端 Bot 管理系统的 CRUD 操作
  • C++ 实现类似 Java 的 Stream API

相关免费在线工具

  • Keycode 信息

    查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online

  • Escape 与 Native 编解码

    JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online

  • JavaScript / HTML 格式化

    使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online

  • JavaScript 压缩与混淆

    Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online

  • 加密/解密文本

    使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online

  • Gemini 图片去水印

    基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印，支持批量处理与下载。 在线工具，Gemini 图片去水印在线工具，online