BFS：解决多源最短路问题

2024-06-23 22:04
文章标签 bfs 多源 短路 解决 问题

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

文章目录

  • 什么是多源最短路问题？
  • 1.矩阵
  • 2.飞地的数量
  • 3.地图的最高点
  • 4.地图分析
  • 总结

在这里插入图片描述

什么是多源最短路问题？

多源最短路问题（Multi-Source Shortest Path Problem，MSSP）是图论中的一个经典问题，它的目标是在给定图中找到从多个源点到所有其他顶点的最短路径。这个问题可以视为单源最短路问题（Single-Source Shortest Path Problem, SSSP）的扩展。
什么是单源最短路问题呢？其实我们上次讲的就可以归结在单元最短路问题当中，其实单源最短路问题就是只有一个起点对应一个终点，求最短路径，而多源最短路问题则是多个起点，对应一个终点，求这多个起点到达终点的最短路径，那这种题我们该怎么做呢？
第一种做法就是将多源最短路问题转换为n个单源最短路问题，循环n次就解决了，但是这种做法是非常慢的。
第二种做法就是把多个节点看成一个整体进行一次单源最短路问题的解法。
这是单源最短路问题问题：
在这里插入图片描述
多源最短路问题：
在这里插入图片描述
我们可以将多源最短路问题的节点看成一个整体，这种方法不仅在计算机领域很常用，在物理数学也很常用，这种方法叫隔离法，我们可以忽略每个节点之间的差异省去了我们比较每个节点差异的过程。

1.矩阵

题目链接
题目：

在这里插入图片描述

样例输出和输入：

在这里插入图片描述

这道题大致的意思就是对一个矩阵做变化，这个矩阵中的数只有两种，一种是1一种是0，我们该如何变换呢？根据题意，变换后节点的值为当前节点的值离最近一个0的节点的距离。按照这个规律首先我们来看看下面的例子，首先零肯定是不会变的，因为零距离最近的零就是他本身，所以这里距离就是0，第二行的1距离最近的零很显然是上左右的零，距离都是1，第三行的1距离醉经的0是上面的0距离为1，但是第三行中间的零距离最近的零是2.
在这里插入图片描述

算法原理：
这里我们已经讲过了做这种题的模式，我们只需要先将所有的零全入到队列中，这些零看成一个整体，在入队列的过程中顺便可以把需要返回的distance数组初始化为-1，然后零的对应位置赋值为0，这里我们直接利用单元最短路向外广搜，也就是整体向外扩散。
在这里插入图片描述
这里红色部分表示我们第一次入进去的0，蓝色部分表示我们第一次扩散，第一次扩散出来的部分应该填1，然后接下来可以继续向外扩散，这里就不展示了。

代码展示：

class Solution {
public:typedef pair<int, int> PII;int dx[4] = { 0,0,1,-1 };int dy[4] = { 1,-1,0,0 };vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {int m = mat.size();int n = mat[0].size();vector<vector<int>> distance(m, vector<int>(n, -1));queue<PII> q;for (int i = 0;i < m;i++){for (int j = 0;j < n;j++){if (mat[i][j] == 0){q.push({ i,j });distance[i][j] = 0;}}}while (q.size()){auto [a, b] = q.front();q.pop();for (int i = 0;i < 4;i++){int x = a + dx[i];int y = b + dy[i];if (x >= 0 && x < m && y >= 0 && y < n&& distance[x][y] == -1){distance[x][y] = distance[a][b] + 1;q.push({ x,y });}}}return distance;}
};

2.飞地的数量

题目链接
题目：

在这里插入图片描述

样例输出和输入：

在这里插入图片描述

这道题的大致意思就是让我们找于边界不联通的1的部分，可以看见第一个例子中的1于外界联通，所以这个1不是最终结果，示例1的三个1周围都是1,1代表海洋，所以这三个1和外界不联通所以这三个1是合法的1，返回这三个1，就是返回3.
算法原理：
在这里插入图片描述
上面这个例子红色代表边界上的与外界相连的1，蓝色代表周围都是0的1，这个例子很显然是返回1的，但是如果我们正面做的话很难，因为我们不知道它是否是与外界相连的，只有把这个岛屿遍历完了才知道是与外界相连的，所以这道题我们正难则反找中间的岛屿不好找，我们直接先把与外界相连的岛屿给标记了，然后对这个二维数组遍历一遍，返回没有被标记过的1的个数。这里具体一点就是对这个二维数组最外面的一层用一次多源BFS，先把所有在外面的1入进队列中，然后并标记，表示这个1已经被访问过了，并且不是内部的岛屿，然后再遍历一遍数组，找到没有被标记的1的个数。
代码展示：

class Solution 
{
public:typedef pair<int,int> PII;bool vis[501][501];int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int m,n;int numEnclaves(vector<vector<int>>& grid) {queue<PII> q;m=grid.size();n=grid[0].size();for(int i=0;i<m;i++){if(grid[i][0]==1){q.push({i,0});vis[i][0]=true;}if(grid[i][n-1]==1){q.push({i,n-1});vis[i][n-1]=true;}}for(int i=0;i<n;i++){if(grid[0][i]==1){q.push({0,i});vis[0][i]=true;}if(grid[m-1][i]==1){q.push({m-1,i});vis[m-1][i]=true;}}while(q.size()){auto [a,b]=q.front();q.pop();for(int i=0;i<4;i++){int x=a+dx[i];int y=b+dy[i];if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1&&vis[x][y]==false){q.push({x,y});vis[x][y]=true;}}}int step=0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1&&vis[i][j]==false){step++;}}}return step;}
};

3.地图的最高点

题目链接
题目：

在这里插入图片描述

这道题其实是和第一道题是一样的
样例输出和输入：

在这里插入图片描述

这道题和第一题比较相似。
在这里插入图片描述
我们来看示例2，首先很明显，这道题需要我们返回一个二维矩阵，然后每个元素的特点就是距离最近的一个1的距离，很显然给出的示例中，1里1最近当然就返回的是0，第一个0距离最近的也是1，所以我们只需要照搬第一个题的算法即可，可以说和第一个题一模一样。

代码展示：

class Solution 
{
public:typedef pair<int,int> PII;int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int m,n;vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {m=isWater.size();n=isWater[0].size();vector<vector<int>> answer(m,vector<int>(n,-1));queue<PII> q;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(isWater[i][j]==1){answer[i][j]=0;q.push({i,j});}}}while(q.size()){auto [a,b]=q.front();q.pop();for(int i=0;i<4;i++){int x=a+dx[i];int y=b+dy[i];if(x>=0&&x<m&&y>=0&&y<n&&answer[x][y]==-1){q.push({x,y});answer[x][y]=answer[a][b]+1;}}}return answer;}
};

4.地图分析

题目链接
题目：

在这里插入图片描述

样例输出和输入：

在这里插入图片描述

这道题其实也是和第一道题一样的但是这道题要求变化后的二维数组中最大的那个数，并返回。

代码展示：

class Solution {
public:typedef pair<int,int> PII;int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int m,n;int maxDistance(vector<vector<int>>& grid) {m=grid.size();n=grid[0].size();vector<vector<int>> dist(m,vector<int>(n,-1));queue<PII> q;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1){q.push({i,j});dist[i][j]=0;}}}int Max=-1;while(q.size()){auto [a,b]=q.front();q.pop();for(int i=0;i<4;i++){int x=a+dx[i];int y=b+dy[i];if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==0&&dist[x][y]==-1){q.push({x,y});dist[x][y]=dist[a][b]+1;Max=dist[x][y];    }}}return Max;}
};

总结

通过本文对BFS算法在解决多源最短路问题中的应用介绍，可以看出BFS在处理无权图的最短路径问题时具有显著优势。它不仅操作简单、直观易懂，而且其广度优先的特点使得它在寻找最短路径时非常高效。多源最短路问题在实际生活中有着广泛的应用，例如交通网络中的最短路径计算、社交网络中的影响力传播等。

在实现过程中，我们需要注意以下几点：

初始化多源节点：确保所有源节点都被正确加入队列，并且其初始距离设置为0。
处理并行搜索：合理安排队列的扩展，保证所有节点都能被正确访问。
避免重复访问：使用访问标记或距离数组来避免节点被重复处理，提高算法效率。
通过实际案例，我们可以看到BFS在解决多源最短路问题时的高效性和可靠性。希望通过这篇文章，读者能够更好地理解BFS算法的应用场景及其实现方法，为今后的算法学习和实际应用提供帮助。

如有任何疑问或建议，欢迎在评论区留言讨论。

这篇关于BFS：解决多源最短路问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1088399。

相关文章

linux生产者，消费者问题

linux生产者，消费者问题

pthread_cond_wait() ：用于阻塞当前线程，等待别的线程使用pthread_cond_signal()或pthread_cond_broadcast来唤醒它。 pthread_cond_wait() 必须与pthread_mutex 配套使用。pthread_cond_wait()函数一进入wait状态就会自动release mutex。当其他线程通过pthread
阅读更多...
问题：第一次世界大战的起止时间是 #其他#学习方法#微信

问题：第一次世界大战的起止时间是 #其他#学习方法#微信

问题：第一次世界大战的起止时间是 A.1913 ~1918 年 B.1913 ~1918 年 C.1914 ~1918 年 D.1914 ~1919 年 参考答案如图所示
阅读更多...
2024.6.24 IDEA中文乱码问题（服务器 控制台 TOMcat）实测已解决

2024.6.24 IDEA中文乱码问题（服务器 控制台 TOMcat）实测已解决

1.问题产生原因： 1.文件编码不一致：如果文件的编码方式与IDEA设置的编码方式不一致，就会产生乱码。确保文件和IDEA使用相同的编码，通常是UTF-8。2.IDEA设置问题：检查IDEA的全局编码设置和项目编码设置是否正确。3.终端或控制台编码问题：如果你在终端或控制台看到乱码，可能是终端的编码设置问题。确保终端使用的是支持你的文件的编码方式。 2.解决方案： 1.File -> S
阅读更多...
vcpkg安装opencv中的特殊问题记录（无法找到opencv_corexd.dll）

vcpkg安装opencv中的特殊问题记录（无法找到opencv_corexd.dll）

我是按照网上的vcpkg安装opencv方法进行的（比如这篇：从0开始在visual studio上安装opencv（超详细，针对小白）），但是中间出现了一些别人没有遇到的问题，虽然原因没有找到，但是本人给出一些暂时的解决办法： 问题1： 我在安装库命令行使用的是 .\vcpkg.exe install opencv 我的电脑是x64，vcpkg在这条命令后默认下载的也是opencv2:x6
阅读更多...
问题-windows-VPN不正确关闭导致网页打不开

问题-windows-VPN不正确关闭导致网页打不开

为什么会发生这类事情呢？ 主要原因是关机之前vpn没有关掉导致的。 至于为什么没关掉vpn会导致网页打不开，我猜测是因为vpn建立的链接没被更改。 正确关掉vpn的时候，会把ip链接断掉，如果你不正确关掉，ip链接没有断掉，此时你vpn又是没启动的，没有域名解析，所以就打不开网站。 你可以在打不开网页的时候，把vpn打开，你会发现网络又可以登录了。 方法一 注意：方法一虽然方便，但是可能会有
阅读更多...
多源 BFS

多源 BFS

例题一 解法（bfs）（多个源头的最短路问题） 算法思路： 对于求的最终结果，我们有两种⽅式： • 第⼀种⽅式：从每⼀个 1 开始，然后通过层序遍历找到离它最近的 0 。 这⼀种⽅式，我们会以所有的 1 起点，来⼀次层序遍历，势必会遍历到很多重复的点。并且如果 矩阵中只有⼀个 0 的话，每⼀次层序遍历都要遍历很多层，时间复
阅读更多...
vue同页面多路由懒加载-及可能存在问题的解决方式

vue同页面多路由懒加载-及可能存在问题的解决方式

先上图，再解释 图一是多路由页面，图二是路由文件。从图一可以看出每个router-view对应的name都不一样。从图二可以看出层路由对应的组件加载方式要跟图一中的name相对应，并且图二的路由层在跟图一对应的页面中要加上components层，多一个s结尾，里面的的方法名就是图一路由的name值，里面还可以照样用懒加载的方式。 页面上其他的路由在路由文件中也跟图二是一样的写法。 附送可能存在
阅读更多...
vue+elementui分页输入框回车与页面中@keyup.enter事件冲突解决

vue+elementui分页输入框回车与页面中@keyup.enter事件冲突解决

解决这个问题的思路只要判断事件源是哪个就好。el分页的回车触发事件是在按下时，抬起并不会再触发。而keyup.enter事件是在抬起时触发。 so，找不到分页的回车事件那就拿keyup.enter事件搞事情。只要判断这个抬起事件的$event中的锚点样式判断不等于分页特有的样式就可以了 @keyup.enter="allKeyup($event)" //页面上的//js中allKeyup(e
阅读更多...
vue+elementui--$message提示框被dialog遮罩层挡住问题解决

vue+elementui--$message提示框被dialog遮罩层挡住问题解决

最近碰到一个先执行this.$message提示内容，然后接着弹出dialog带遮罩层弹框。那么问题来了，message提示框会默认被dialog遮罩层挡住，现在就是要解决这个问题。 由于都是弹框，问题肯定是出在z-index比重问题。由于用$message方式是写在js中而不是写在html中所以不是很好直接去改样式。 不过好在message组件中提供了customClass 属性，我们可以利用
阅读更多...
Visual Studio中，MSBUild版本问题

Visual Studio中，MSBUild版本问题

假如项目规定了MSBUild版本，那么在安装完Visual Studio后，假如带的MSBUild版本与项目要求的版本不符合要求，那么可以把需要的MSBUild添加到系统中，然后即可使用。步骤如下：            假如项目需要使用V12的MSBUild，而安装的Visual Studio带的MSBUild版本为V14。 ①到MSDN下载V12 MSBUild包，把V12包解压到目录（
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2