【算法】【优选算法】多源BFS
目录
一、多源BFS
单源最短路：只有一个起点到终点的最短路问题。
多源最短路问题：有多个起点到终点的最短路问题。
多源BFS：用BFS来解决边权相同的多源最短路问题。
解法：
- 暴力解题，把多源最短路问题，转化为若干个单源最短路问题。
- 把所有起点当成一个起点，问题就变成了单源最短路问题。
二、542.01 矩阵
题目链接：542.01 矩阵
题目描述：
题目解析：
- 给一个只有0 1 的二维数组，计算其中每一个元素到0的最短距离，自己是0距离就是0，将距离存入一个相同规模二维数组的下标中。
法一：
解题思路：
- 我们如果遍历数组，找到1后，就进行求该元素到0的最短距离。
- 求最短距离就使用前面求权值相同的最短距离的方法即可。
- 但是会超时。
解题代码：
//时间复杂度：O(M*N*M*N)//空间复杂度：O(M*N)classSolution{int[] dx ={0,0,1,-1};int[] dy ={1,-1,0,0};int m,n;publicint[][]updateMatrix(int[][] mat){ m = mat.length; n = mat[0].length;int[][] ret =newint[m][n];//遍历mat，遍历到1找最近的0，for(int i =0; i < m; i++){for(int j =0; j < n; j++){if(0== mat[i][j]){ ret[i][j]=0;}else{ ret[i][j]=bfs(mat,i,j);}}}return ret;}publicintbfs(int[][] mat,int x,int y){Queue<int[]> queue =newLinkedList<>(); queue.add(newint[]{x,y});boolean[][] flag =newboolean[m][n]; flag[x][y]=true;int ret =0;while(!queue.isEmpty()){ ret++;int size = queue.size();while(size--!=0){int[] arr = queue.poll();for(int i =0; i <4; i++){int a = arr[0]+ dx[i];int b = arr[1]+ dy[i];//入队if(a >=0&& a < m && b >=0&& b < n &&!flag[a][b]&& mat[a][b]!=0){ flag[a][b]=true; queue.add(newint[]{a,b});}//结束条件if(a >=0&& a < m && b >=0&& b < n && mat[a][b]==0)return ret;}}}return0;}}法二：
解题思路：
- 我们先将数组中的所有0下标，记录下来放入队列中。
- 然后我们层序遍历，每一次循环遍历完当前队列中的值，往外BFS寻找没被标记的1，寻找的循环次数就是这个1的最短距离。
解题代码：
//时间复杂度：O(M*N)//空间复杂度：O(M*N)classSolution{int[] dx ={0,0,1,-1};int[] dy ={1,-1,0,0};publicint[][]updateMatrix(int[][] mat){int m = mat.length;int n = mat[0].length;int[][] ret =newint[m][n];boolean[][] flag =newboolean[m][n];Queue<int[]> queue =newLinkedList<>();//遍历mat，先把0全部放入队列，for(int i =0; i < m; i++){for(int j =0; j < n; j++){if(0== mat[i][j]){ queue.add(newint[]{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(newint[]{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)classSolution{int[] dx =newint[]{0,0,1,-1};int[] dy =newint[]{1,-1,0,0};publicint[][]updateMatrix(int[][] mat){int m = mat.length;int n = mat[0].length;int[][] ret =newint[m][n];Queue<int[]> queue =newLinkedList<>();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(newint[]{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(newint[]{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)classSolution{int[] dx =newint[]{0,0,1,-1};int[] dy =newint[]{1,-1,0,0};publicintnumEnclaves(int[][] grid){int m = grid.length;int n = grid[0].length;Queue<int[]> queue =newLinkedList<>();boolean[][] flag =newboolean[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(newint[]{i,j}); flag[i][j]=true; ret--;}elseif(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(newint[]{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)classSolution{int[] dx =newint[]{0,0,1,-1};int[] dy =newint[]{1,-1,0,0};publicint[][]highestPeak(int[][] isWater){int m = isWater.length;int n = isWater[0].length;int[][] height =newint[m][n];Queue<int[]> queue =newLinkedList<>();//遍历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(newint[]{i,j});}}}//BFSwhile(!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入队，值为出队列元素加1if(x >=0&& x < m && y >=0&& y < n && height[x][y]==-1){ height[x][y]= height[arr[0]][arr[1]]+1; queue.add(newint[]{x,y});}}}return height;}}五、1162. 地图分析
题目链接：1162. 地图分析
题目描述：
题目解析：
- 给我们一个grid数组，只有0 1
- 找出 0 通过上下左右走到最近的1 的距离的最大值
解题思路：
- 一个最经典的多源BFS
- 我们从1开始走（将1全部入队），每走一次（将当前队列元素出完，将元素上下左右的没标记过的0入队），直到走完所有元素，最后走的次数就是结果。
解题代码：
//时间复杂度：O(M*N)//空间复杂度：O(M*N)classSolution{int[] dx =newint[]{0,0,1,-1};int[] dy =newint[]{1,-1,0,0};publicintmaxDistance(int[][] grid){int m = grid.length;int n = grid[0].length;int ret =0;Queue<int[]> queue =newLinkedList<>();boolean[][] flag =newboolean[m][n];//所有1入队for(int i =0; i < m; i++){for(int j =0; j < n; j++){if(grid[i][j]==1){ queue.add(newint[]{i,j}); flag[i][j]=true; ret++;}}}//判断是否全0或全1if(ret ==0|| ret == m * n)return-1; ret =-1;//BFSwhile(!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(newint[]{x,y}); flag[x][y]=true;}}}}return ret;}}
