多源 BFS 详解

2024-06-02 15:12
文章标签 详解 bfs 多源

本文主要是介绍多源 BFS 详解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

一、多源与单源的区别

二、例题练习

2.1 例题1:01 矩阵

2.2 例题2:飞地的数量

2.3 例题3:地图中的最高点 

2.4 例题4:地图分析


一、多源与单源的区别

单源最短路问题如何解决已经在上篇博客给出BFS 解决最短路问题,如果还没学习单源的建议先学习,因为多源就是在单源的基础上进行一些改动即可,即把多个源点一起放入队列中。

• 注意:

多源 BFS 只能用来解决边权为 1 (其实只要边权相等即可,可以转化为边权 1 来解决)的多源最短路问题。如果是边权不相等的情况那么就要使用到图论里面的 Floyd-Warshall 算法,这个后续会写到。

那么该如何解决多源 BFS 问题呢?

解法1:暴力,直接把多源最短路问题转化为若干个单源最短路问题,这个大概率是会超时的,因为重复查找的次数非常多。

解法2:把所有的源点当成一个 “超级源点”,那么问题就变成了单一的单源最短路问题。

如何证明正确性呢? 

理性:严格的证明,这些在一些算法书上能够找到,比较麻烦,文章主要写,如何来做题。故我们就感性的理解一下。

感性:就好比如下图这些性能相同的汽车(把汽车看成开始的源点),如果采用单源最短路的解决思路就是一辆一辆车启动,最后比较谁先到终点。如果采用多源最短路的解题思路就是把这些车一起启动,谁先到终点,就是最短路。这里可能有的友友会问,这样和单源最短路的时间复杂度不是一样的嘛?其实当在同一条路上如果有节点在前面,那么后面的节点就可以直接舍去,因为绝对不可能是最短路。

二、例题练习

2.1 例题1:01 矩阵

• 题目链接:01 矩阵

• 问题描述:

给定一个由 0 和 1 组成的矩阵 mat ,请输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

• 解题思路:

如果采用单源最短路(一个位置一个位置的去求)的话会超时(替大家试过了),正确的解法多源 BFS + 正难则反(填表更快),把所有的 0 当成起点,1当作终点(终点可以有多个)。找到一个 1 且是没有被遍历过的就可以把路径数直接填入,因为绝对没有比这个更小的路径了。

• 代码编写:

直接把最开始创建的数组都初始化成 -1 ,这样就不用创建一个 vis 表来标记已经走过的节点。且路径数可以直接在原来的路径数上 + 1 即可,一举两得。具体代码如下:

class Solution {int[] dx = {0,0,1,-1};int[] dy = {1,-1,0,0};public int[][] updateMatrix(int[][] mat) {//1.把所有为0的元素存入队列int n = mat.length;int m = mat[0].length;//2.创建 dest 数组//3.dest初始化为 - 1int[][] dest = new int[n][m];for(int i = 0;i < n;i++){Arrays.fill(dest[i],-1);}Queue<int[]> q = new LinkedList<>();for(int i = 0;i < n;i++){for(int j = 0;j < m;j++){if(mat[i][j] == 0){dest[i][j] = 0;q.add(new int[]{i,j});}}}//4.bfswhile(!q.isEmpty()){int[] tmp = q.poll();int a = tmp[0],b = tmp[1];for(int k = 0;k < 4;k++){int x = a + dx[k];int y = b + dy[k];if(x >= 0 && x < n && y >= 0 && y < m && dest[x][y] == -1){if(mat[x][y] == 1){//5.在原来的基础上直接 + 1dest[x][y] = dest[a][b] + 1;}q.add(new int[]{x,y});}}}return dest;}
}

2.2 例题2:飞地的数量

• 题目链接:飞地的数量

• 问题描述:

给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

• 解题思路:

正难则反: 从边上的 1 开始搜索,把与边上 1 相连的联通区域全部标记⼀下,然后再遍历⼀遍矩阵,看看哪些位置的 1 没有被标记即可,标记的时候,可以用多源 bfs 解决(这题单源或者 DFS都行)。

• 代码编写:

class Solution {int n,m;int[] dx = {0,0,1,-1};int[] dy = {1,-1,0,0};public int numEnclaves(int[][] grid) {n = grid.length;m = grid[0].length;//1.拿所有边界的1进行一次bfs标记Queue<int[]> q = new LinkedList<>();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){//这么写比较快且不容易出错if(grid[i][j] == 1){q.add(new int[]{i,j});}}}}//直接改为2即可while(!q.isEmpty()){int size = q.size();for(int i = 0;i < size;i++){int[] tmp = q.poll();int a = tmp[0],b = tmp[1];grid[a][b] = 2;for(int k = 0;k < 4;k++){int x = a + dx[k];int y = b + dy[k];if(x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1){q.add(new int[]{x,y});grid[x][y] = 2;}}}}//2.最后遍历如果为 1 且未被标记的话ret++int ret = 0;//最后的结果for(int i = 0;i < n;i++){for(int j = 0;j < m;j++){if(grid[i][j] == 1){ret++;}}}//3.返回 retreturn ret;}
}

2.3 例题3:地图中的最高点 

• 题目链接:地图中的最高点

• 问题描述:

给你一个大小为 m x n 的整数矩阵 isWater ,它代表了一个由 陆地 和 水域 单元格组成的地图。

  • 如果 isWater[i][j] == 0 ,格子 (i, j) 是一个 陆地 格子。
  • 如果 isWater[i][j] == 1 ,格子 (i, j) 是一个 水域 格子。

你需要按照如下规则给每个单元格安排高度:

  • 每个格子的高度都必须是非负的。
  • 如果一个格子是 水域 ,那么它的高度必须为 0 。
  • 任意相邻的格子高度差 至多 为 1 。当两个格子在正东、南、西、北方向上相互紧挨着,就称它们为相邻的格子。(也就是说它们有一条公共边)

找到一种安排高度的方案,使得矩阵中的最高高度值 最大 。

请你返回一个大小为 m x n 的整数矩阵 height ,其中 height[i][j] 是格子 (i, j) 的高度。如果有多种解法,请返回 任意一个 。

• 解题思路:

01矩阵的变型题,直接用多源 bfs 解决即可。任意相邻的格子高度差 至多 为 1,这个条件非常重要,因为有这个条件我们才能确定这题其实是用最短路的思路来解决。具体就是把所有水域的格子添加到队列中,一层一层遍历即可。

• 代码编写:

class Solution {int[] dx = {0,0,1,-1};int[] dy = {1,-1,0,0};public int[][] highestPeak(int[][] isWater) {//多源 bfsint n = isWater.length;int m = isWater[0].length;int[][] ans = new int[n][m];//3.把返回数组初始化为 -1for(int i = 0;i < n;i++){Arrays.fill(ans[i],-1);}//1.找到所有的值为 1 的加入 bfsQueue<int[]> q = new LinkedList<>();for(int i = 0;i < n;i++){for(int j = 0;j < m;j++){if(isWater[i][j] == 1){ans[i][j] = 0;q.add(new int[]{i,j});}}}while(!q.isEmpty()){int size = q.size();for(int i = 0;i < size;i++){int[] tmp = q.poll();int a = tmp[0],b = tmp[1];//这个地方不用再填值了for(int k = 0;k < 4;k++){int x = a + dx[k];int y = b + dy[k];if(x >= 0 && x < n && y >= 0 && y < m && ans[x][y] == -1 && isWater[x][y] == 0){ans[x][y] = ans[a][b] + 1;//直接在原来的数值上 + 1 即可//不用再来一个timeq.add(new int[]{x,y});}}}}//4.返回答案return ans;}
}

2.4 例题4:地图分析

• 题目链接:地图分析

• 问题描述:

你现在手里有一份大小为 n x n 的 网格 grid,上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋,1 代表陆地。

请你找出一个海洋单元格,这个海洋单元格到离它最近的陆地单元格的距离是最大的,并返回该距离。如果网格上只有陆地或者海洋,请返回 -1

我们这里说的距离是「曼哈顿距离」( Manhattan Distance):(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

• 解题思路:

正难则反,把所有 1 的节点都进队,这样一次就可以把所有的 0 都填好(路径数)。和上面几题都差不多,多源 BFS 代码编写倒是不难,主要是要先转化一下,怎么把那么多节点变成 “超级源点”。

• 代码编写:

class Solution {int[] dx = {0,0,1,-1};int[] dy = {1,-1,0,0};public int maxDistance(int[][] grid) {//多源 bfsint n = grid.length;int m = grid[0].length;boolean[][] vis = new boolean[n][m];//1.把 1 进 bfsQueue<int[]> q = new LinkedList<>();for(int i = 0;i < n;i++){for(int j = 0;j < m;j++){if(grid[i][j] == 1){q.add(new int[]{i,j});}}}if(q.size() == 0 || q.size() == (n * m)){return -1;}int time = 0;//2.time计数while(!q.isEmpty()){int size = q.size();time++;for(int i = 0;i < size;i++){int[] tmp = q.poll();int a = tmp[0],b = tmp[1];vis[a][b] = true;for(int k = 0;k < 4;k++){int x = a + dx[k],y = b + dy[k];if(x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && grid[x][y] == 0){q.add(new int[]{x,y});//3.vis 去重vis[x][y] = true;}}}}return time - 1;}
}

• 小结:和单源 BFS 找最短路的模板基本一样,只要多加练习,代码编写是很简单的,重要的是思路,哪些题目可以使用多源 BFS 来解决,这个就需要多做题了👍👍👍。

结语:

其实写博客不仅仅是为了教大家,同时这也有利于我巩固知识点,和做一个学习的总结,由于作者水平有限,对文章有任何问题还请指出,非常感谢。如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注,这可以激励我写出更加优秀的文章。

这篇关于多源 BFS 详解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1024324

相关文章

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Java中的JSONObject详解

《Java中的JSONObject详解》:本文主要介绍Java中的JSONObject详解,需要的朋友可以参考下... Java中的jsONObject详解一、引言在Java开发中,处理JSON数据是一种常见的需求。JSONObject是处理JSON对象的一个非常有用的类,它提供了一系列的API来操作J

HTML5中的Microdata与历史记录管理详解

《HTML5中的Microdata与历史记录管理详解》Microdata作为HTML5新增的一个特性,它允许开发者在HTML文档中添加更多的语义信息,以便于搜索引擎和浏览器更好地理解页面内容,本文将探... 目录html5中的Mijscrodata与历史记录管理背景简介html5中的Microdata使用M

html5的响应式布局的方法示例详解

《html5的响应式布局的方法示例详解》:本文主要介绍了HTML5中使用媒体查询和Flexbox进行响应式布局的方法,简要介绍了CSSGrid布局的基础知识和如何实现自动换行的网格布局,详细内容请阅读本文,希望能对你有所帮助... 一 使用媒体查询响应式布局        使用的参数@media这是常用的

HTML5表格语法格式详解

《HTML5表格语法格式详解》在HTML语法中,表格主要通过table、tr和td3个标签构成,本文通过实例代码讲解HTML5表格语法格式,感兴趣的朋友一起看看吧... 目录一、表格1.表格语法格式2.表格属性 3.例子二、不规则表格1.跨行2.跨列3.例子一、表格在html语法中,表格主要通过< tab

Linux之计划任务和调度命令at/cron详解

《Linux之计划任务和调度命令at/cron详解》:本文主要介绍Linux之计划任务和调度命令at/cron的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux计划任务和调度命令at/cron一、计划任务二、命令{at}介绍三、命令语法及功能 :at

Java使用SLF4J记录不同级别日志的示例详解

《Java使用SLF4J记录不同级别日志的示例详解》SLF4J是一个简单的日志门面,它允许在运行时选择不同的日志实现,这篇文章主要为大家详细介绍了如何使用SLF4J记录不同级别日志,感兴趣的可以了解下... 目录一、SLF4J简介二、添加依赖三、配置Logback四、记录不同级别的日志五、总结一、SLF4J