【算法题】多源BFS

多源BFS将所有满足条件的起点同时入队（视为“第0层”），再按层扩散，能高效解决“多个源点到网格中各点的最短距离”“全局最短/最长距离”“边界连通域标记”等问题。其核心优势是：仅需一次遍历即可完成所有源点的扩散，时间复杂度与单源BFS一致（O(mn)O(mn)O(mn)），远优于“对每个点做单源BFS”的暴力解法（O((mn)2)O((mn)^2)O((mn)2)）。本文通过4道经典多源BFS题目，拆解多源BFS的核心框架与场景化适配技巧。

一、01矩阵（更新矩阵）

题目描述：给定一个由0和1组成的矩阵mat，将每个1替换为到最近0的最短距离，0保持不变，返回更新后的矩阵。

核心思路：多源BFS求最短距离
普通单源BFS只能求“一个0”到各点的距离，而本题需要“所有0”到各1的最短距离——将所有0作为同时出发的起点（距离为0），入队后按层扩散，每个1第一次被访问时的距离，就是到最近0的最短距离（多源扩散保证了“最短”）。

代码解析：

classSolution{intm,n;intdx[4]={0,0,1,-1};// 上下左右方向数组intdy[4]={1,-1,0,0};public:vector<vector<int>>updateMatrix(vector<vector<int>>&mat){m=mat.size(),n=mat[0].size();vector<vector<int>>dist(m,vector(n,-1));// 距离数组：-1表示未访问queue<pair<int,int>>q;// 步骤1：所有0作为起点入队，距离设为0for(inti=0;i<m;i++)for(intj=0;j<n;j++)if(mat[i][j]==0){dist[i][j]=0;q.push({i,j});}// 步骤2：多源BFS扩散while(q.size()){auto[a,b]=q.front();q.pop();for(inti=0;i<4;i++){intx=a+dx[i],y=b+dy[i];// 边界检查 + 未访问（保证第一次访问是最短距离）if(x>=0&&y>=0&&x<m&&y<n&&dist[x][y]==-1){dist[x][y]=dist[a][b]+1;// 邻接节点距离=当前+1q.push({x,y});}}}returndist;}};

关键细节：

• dist数组既记录距离，又充当“访问标记”（-1=未访问），无需额外开vis数组；
• 多源同时扩散，确保每个1被“最近的0”先访问，距离即为最短。

二、飞地数量（numEnclaves）

题目描述：给定01矩阵，“飞地”是指无法从边界的1到达的内部1，求飞地的数量。

核心思路：反向多源BFS标记连通域
飞地的本质是“不与边界1连通的内部1”——反向思考：将所有边界的1作为多源起点，标记所有可达的1，最后统计未被标记的1的数量即为飞地数。

代码解析：

classSolution{intdx[4]={0,0,1,-1};intdy[4]={1,-1,0,0};public:intnumEnclaves(vector<vector<int>>&grid){intm=grid.size(),n=grid[0].size();vector<vector<bool>>vis(m,vector<bool>(n));// 访问标记：是否与边界1连通queue<pair<int,int>>q;// 步骤1：所有边界的1作为起点入队并标记for(inti=0;i<m;i++)for(intj=0;j<n;j++)if(i==0||j==0||i==m-1||j==n-1)// 边界坐标{if(grid[i][j]==1){q.push({i,j});vis[i][j]=true;}}// 步骤2：多源BFS标记所有可达的1while(q.size()){auto[a,b]=q.front();q.pop();for(inti=0;i<4;i++){intx=a+dx[i],y=b+dy[i];// 边界检查 + 未标记 + 是1if(x>=0&&y>=0&&x<m&&y<n&&!vis[x][y]&&grid[x][y]==1){vis[x][y]=true;q.push({x,y});}}}// 步骤3：统计未被标记的1（飞地）intret=0;for(inti=0;i<m;i++)for(intj=0;j<n;j++)if(!vis[i][j]&&grid[i][j]==1)ret++;returnret;}};

关键细节：

• 反向多源的核心是“标记不需要的部分”，剩余未标记的即为目标；
• 仅遍历边界坐标作为起点，避免无效遍历。

三、最高海拔（highestPeak）

题目描述：给定矩阵isWater（1=水域，0=陆地），要求为每个陆地分配海拔：

1. 水域海拔为0；
2. 相邻单元格海拔差≤1；
3. 海拔尽可能大。

核心思路：多源BFS求“最远最近距离”
满足“相邻差≤1且海拔最大”的唯一解是：每个陆地的海拔 = 到最近水域的最短距离（多源BFS的天然结果）。这道题是“01矩阵”的语义变体，逻辑完全一致。

代码解析：

classSolution{intdx[4]={0,0,1,-1};intdy[4]={1,-1,0,0};public:vector<vector<int>>highestPeak(vector<vector<int>>&isWater){intm=isWater.size(),n=isWater[0].size();vector<vector<int>>dist(m,vector(n,-1));// dist数组存储海拔queue<pair<int,int>>q;// 步骤1：所有水域（1）作为起点，海拔设为0for(inti=0;i<m;i++)for(intj=0;j<n;j++)if(isWater[i][j]==1){dist[i][j]=0;q.push({i,j});}// 步骤2：多源BFS扩散，海拔=最近水域距离+1while(q.size()){auto[a,b]=q.front();q.pop();for(inti=0;i<4;i++){intx=a+dx[i],y=b+dy[i];if(x>=0&&y>=0&&x<m&&y<n&&dist[x][y]==-1){dist[x][y]=dist[a][b]+1;q.push({x,y});}}}returndist;}};

关键细节：

• 语义转换：“海拔”=“到最近水域的最短距离”，完全复用01矩阵的多源BFS逻辑；
• 无需额外条件，多源扩散的结果天然满足“相邻差≤1”和“海拔最大”。

四、海洋陆地最远距离（maxDistance）

题目描述：给定01矩阵（1=陆地，0=海洋），求海洋到最近陆地的最远距离；若全是陆地/全是海洋，返回-1。

核心思路：多源BFS求全局最大最短距离
所有陆地作为多源起点，计算每个海洋到最近陆地的最短距离，最后取这些距离的最大值即为答案。

代码解析：

classSolution{intdx[4]={0,0,1,-1};intdy[4]={1,-1,0,0};public:intmaxDistance(vector<vector<int>>&grid){intm=grid.size(),n=grid[0].size();vector<vector<int>>dist(m,vector(n,-1));queue<pair<int,int>>q;// 步骤1：所有陆地（1）作为起点入队，距离设为0for(inti=0;i<m;i++)for(intj=0;j<n;j++)if(grid[i][j]==1){dist[i][j]=0;q.push({i,j});}// 步骤2：多源BFS计算最短距离，同时记录最大值intret=-1;while(q.size()){auto[a,b]=q.front();q.pop();for(inti=0;i<4;i++){intx=a+dx[i],y=b+dy[i];if(x>=0&&y>=0&&x<m&&y<n&&dist[x][y]==-1){dist[x][y]=dist[a][b]+1;q.push({x,y});ret=max(ret,dist[x][y]);// 更新最大距离}}}returnret;// 全陆地时ret=-1，全海洋时也为-1，符合要求}};

关键细节：

• 无需额外遍历矩阵找最大值，在BFS过程中实时更新即可；
• 边界条件自然满足：全陆地时没有海洋被访问，ret保持-1；全海洋时q初始为空，ret也为-1。

多源BFS通用框架总结

// 通用框架1.初始化：-距离/访问数组（dist/vis）：-1/False 表示未访问；-队列q，将所有满足条件的多源起点入队，并初始化dist/vis；2.多源扩散：while(队列非空){取出队首节点(a,b);遍历四个方向： 计算邻接节点(x,y);if(边界合法&&未访问){更新dist/vis=当前节点值+1/True;入队(x,y);（可选）更新目标值（如最大距离、计数等）;}}3.结果计算：-最短距离类：直接返回dist数组；-连通域标记类：统计未标记的节点数；-最大距离类：返回BFS中记录的最大值；