C++：bfs解决多源最短路与拓扑排序问题习题

1. 多源最短路

其实就是将所有源头都加入队列，

01矩阵

LCR 107. 01 矩阵 - 力扣（LeetCode）

 思路

求每个元素到离其最近0的距离如果我们将1当做源头加入队列的话，无法处理多个连续1的距离存储，我们反其道而行之，将所有的终点存进队列，遍历离其最近的1，当然如果旁边是0无需入队(因为旁边这个0找到的1肯定比他快一步)，是1才要入队，先遍历到1的步数一定是最小的步数。

ac代码

class Solution {
public:vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {int m=mat.size();//int n=mat[0].size();vector<vector<int>> states(m,vector<int>(n,-1));int dx[4]={1,0,0,-1};int dy[4]={0,1,-1,0};for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(mat[i][j]==0)//从终点开始找{qu.push({i,j});states[i][j]=0;}}}while(!qu.empty()){int x1=qu.front().first;int y1=qu.front().second;qu.pop();for(int i=0;i<4;i++){int x2=x1+dx[i];int y2=y1+dy[i];if(x2<0||x2>=m||y2<0||y2>=n)continue;if(mat[x2][y2]==0||states[x2][y2]!=-1)//同为0或者走过了先走的肯定更小continue;states[x2][y2]=states[x1][y1]+1;qu.push({x2,y2});}}return states;}private:queue<pair<int,int>> qu;};

 飞地的数量

1020. 飞地的数量 - 力扣（LeetCode）

思路

解法1：

(非多源bfs)遍历地图，将遇到的并且没有走过的1进行bfs，如果没有陆地在边缘返回值为连通的陆地数量，在边缘就返回0，将返回值累加起来即可。

解法2：
(多源bfs)先考虑什么可以当源头，所有的1明显不可以，0进去也得不出来结果。我们发现题目的关键点在于边缘的陆地就不是飞地，所以我们将所有在边缘的陆地入队，然后查找与这些陆地相连的其他陆地将其标记，最后遍历地图查找没被标记的陆地即可。

ac代码

class Solution {
public:int bfs(vector<vector<int>>& grid,int x,int y){int m=grid.size();int n=grid[0].size();int dx[4]={1,0,0,-1};int dy[4]={0,1,-1,0};queue<pair<int,int>> qu;qu.push({x,y});states[x][y]=true;int cnt=1;//记录有多少个陆地bool f=true;//如果有边缘就变falsewhile(!qu.empty()){int x1=qu.front().first;int y1=qu.front().second;qu.pop();for(int i=0;i<4;i++){int x2=x1+dx[i];int y2=y1+dy[i];if(x2<0||x2>=m||y2<0||y2>=n){f=false;//有靠边缘的continue;}if(states[x2][y2]!=false||grid[x2][y2]==0)continue;states[x2][y2]=true;//走过qu.push({x2,y2});cnt++;}}if(f)return cnt;elsereturn 0;}int numEnclaves(vector<vector<int>>& grid) {int m=grid.size();int n=grid[0].size();memset(states,false,sizeof states);int sum=0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1&&!states[i][j]){sum+=bfs(grid,i,j);}}}return sum;}private:bool states[510][510];
};

地图分析

1162. 地图分析 - 力扣（LeetCode）

 思路

统计海洋单位与离其最近的陆地的距离，直接将所有陆地视为源头四散记录自己离海洋的距离，即可。每到一个海洋就比较到这个海洋的距离与之前记录的到海洋的距离那个更远。

ac代码

class Solution {
public:int maxDistance(vector<vector<int>>& grid) {int n=grid.size();int dx[4]={1,0,0,-1};int dy[4]={0,-1,1,0};vector<vector<int>> states(n,vector<int>(n,-1));for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(grid[i][j]==1){qu.push({i,j});states[i][j]=0;}}}while(!qu.empty()){int x1=qu.front().first;int y1=qu.front().second;qu.pop();for(int i=0;i<4;i++){int x2=x1+dx[i];int y2=y1+dy[i];if(x2<0||x2>=n||y2<0||y2>=n)continue;if(grid[x2][y2]==1||states[x2][y2]!=-1)//不是陆地，不能走过continue;states[x2][y2]=states[x1][y1]+1;cntmax=max(cntmax,states[x2][y2]);qu.push({x2,y2});}}return cntmax;}private:int cntmax=-1;queue<pair<int,int>> qu;//存陆地};

地图中的最高点

1765. 地图中的最高点 - 力扣（LeetCode）

思路 

题目很直观，将所有的水域入队，然后四处扩散，增加即可。

ac代码

class Solution {
public:vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {int m=isWater.size();//int n=isWater[0].size();vector<vector<int>> states(m,vector<int>(n,-1));int dx[4]={1,0,0,-1};int dy[4]={0,1,-1,0};for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(isWater[i][j]==1)//从水开始{qu.push({i,j});states[i][j]=0;//水域为0}}}while(!qu.empty()){int x1=qu.front().first;int y1=qu.front().second;qu.pop();for(int i=0;i<4;i++){int x2=x1+dx[i];int y2=y1+dy[i];if(x2<0||x2>=m||y2<0||y2>=n)continue;if(isWater[x2][y2]==1||states[x2][y2]!=-1)//都为水域或者走过了先走的肯定更小continue;states[x2][y2]=states[x1][y1]+1;qu.push({x2,y2});}}return states;}private:queue<pair<int,int>> qu;        
};

2. 拓扑排序问题

将问题变成一个有向无环图，解决拓扑排序要找到做事情的先后顺序，结果可能不是唯一的。

如下图

有几个通向自己的节点入度就为几

我们找到图中入度为0的点a，必须将a消除后使b和c的入度也从1变为0才可以消除b和c，必须把b和c都消除后才能将d的入度变为0，再消除b。

实现拓扑排序的具体步骤：

借助队列：queue

1. 初始化：把所有入度为0的点加入到队列中

2. 当队列不为空时：

(1)拿出队头元素加到最终结果上

(2)删除与该元素相连的边

(3)判断删除边相连的点是否入度变为了0，为0就入队

可以创建邻接矩阵来构造图

也可以创建邻接表来构造：vector<vector<int>> 或者 unordered_map<int,vector<int>>

课程表

207. 课程表 - 力扣（LeetCode）

思路

创建一个哈希表来记录每个课程之间的关系将完成x课程的前置课程y1，y2等都存储起来，创建一个数组记录每个课程的入度

ac代码

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {in.resize(numCourses,0);int m=prerequisites.size();for(int i=0;i<m;i++){//数组里只有两个数map[prerequisites[i][1]].push_back(prerequisites[i][0]);//b[i]通向a[i]in[prerequisites[i][0]]++;//a[i]多一个前置条件}for(int i=0;i<in.size();i++){if(in[i]==0)//没前置条件qu.push(i);//将这门课程入队}int cnt=0;while(!qu.empty()){int tmp=qu.front();qu.pop();cnt++;//for(int i=0;i<map[tmp].size();i++)//删除这个前置，其链接的点少一个前置{in[map[tmp][i]]--;if(in[map[tmp][i]]==0)//前置都完成了{qu.push(map[tmp][i]);}}}if(cnt==numCourses)return true;elsereturn false;}private:unordered_map<int,vector<int>> map;//邻接表vector<int> in;//记录每个课程的入度queue<int> qu; 
};

课程表 II

LCR 113. 课程表 II - 力扣（LeetCode）

思路

与上题没什么不同，就是多一个数组来记录可以学习的课程

ac代码

class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {in.resize(numCourses,0);int m=prerequisites.size();for(int i=0;i<m;i++){map[prerequisites[i][1]].push_back(prerequisites[i][0]);//将b[i]后置保存起来in[prerequisites[i][0]]++;//这个课程前置加1}for(int i=0;i<in.size();i++){if(in[i]==0)qu.push(i);}vector<int> nums;while(!qu.empty()){int tmp=qu.front();qu.pop();nums.push_back(tmp);for(int i=0;i<map[tmp].size();i++){in[map[tmp][i]]--;if(in[map[tmp][i]]==0)qu.push(map[tmp][i]);}}if(nums.size()==numCourses)return nums;elsenums.resize(0,0);return nums;}unordered_map<int,vector<int>> map;//邻接表vector<int> in;//记录自身有多少前置queue<int> qu;
};

火星词典

LCR 114. 火星词典 - 力扣（LeetCode）

 思路

如何建图？
将第一个字符串与之后所有字符串对比(双指针一个字符一个字符对比)然后再将第二个字符串与第二个字符串之后所有字符串对比依次类推...，有不一样的就检测哈希表中x字符有没有已经存入相同的前置字符，没有再存进去，然后break再往后也找不出来了；要注意当数组走完并且第二个数组比第一个数组小时是错误的，要特判一下

记录入度

用一个哈希表进行记录

for(auto& [a,b]:in)//in中char会存到a里入度的值会存到b里
//用来遍历in数组

解决问题与上方差不多

ac代码

class Solution {
public:string alienOrder(vector<string>& words) {//所有前置走完走接下来的int m = words.size();for (auto& tmp : words)//初始化入度{for (auto t : tmp){in[t] = 0;}}for (int i = 0; i < m - 1; i++){for (int j = i + 1; j < m; j++){int n=min(words[i].size(),words[j].size());string s1=words[i];string s2=words[j];int t=0;for( t=0;t<n;t++){if(s1[t]!=s2[t])//不相等再存{if(!map[s1[t]].count(s2[t]))//看s1[t]其中有没有存s2[t]{map[s1[t]].insert(s2[t]);in[s2[t]]++;}break;//发现不同就不用往后找了}}if(t==s2.size()&&t<s1.size())return "";}}int cnt=0;for(auto& [a,b]:in)//in中char会存到a里入度的值会存到b里{if(b==0) qu.push(a);cnt++;}string s = "";while (!qu.empty()){char tmp = qu.front();qu.pop();s += tmp;for (auto ch : map[tmp])//遍历哈希表{in[ch]--;if (in[ch] == 0)qu.push(ch);}}if(s.size()==cnt)return s;elsereturn "";}unordered_map<char, unordered_set<char>> map;//unordered_map<char, int> in;//记录这个单词还有多少单词queue<char> qu;
};

---

这篇就到这里了(๑′ᴗ‵๑)Ｉ Lᵒᵛᵉᵧₒᵤ❤