BFS 解决最短路问题(C++)
文章目录
- 前言
- 一、单源最短路问题
- 433. 最小基因变化
- 题目解析
- 算法原理
- 代码编写
- 675. 为高尔夫比赛砍树
- 题目解析
- 算法原理
- 代码编写
- 二、多源最短路问题
- 542. 01 矩阵
- 题目解析
- 算法原理
- 代码编写
- 1020. 飞地的数量
- 题目解析
- 算法原理
- 代码编写
- 总结
前言
一、单源最短路问题
边权相等的最短路。
从起点开始，进行一次BFS操作。需要借助队列和数组（是否遍历过）完成操作。
弹出前，先计算队列中有多少元素，同时向外扩展。
最短路径就是层序遍历的层数
433. 最小基因变化
题目解析
- 最小基因变化添加链接描述
做完上面这道题目可以做一下这道题目。代码放到最后了。
127. 单词接龙
算法原理
本道题木是经典的单源最短路问题，虽然题目没有直接说明，但是经过我们的分析是可以分析出来的。
1.用哈希表来解决转换后是否存在bank中
2.用哈希表判断是否已经转换过了
3.我们每个字符串都有8个位置可以转换，并且每次都有四种选择
4.向外扩展的次数就是我们的结果，要注意队列里面的元素要同时向外扩展。
代码编写
class Solution {
public:
int minMutation(string startGene, string endGene, vector<string>& bank)
{
//哈希表存放，方便快速查找
unordered_set<string> hash(bank.begin(),bank.end());
//特殊情况
if(startGene==endGene) return 0;
if(hash.count(endGene)==0) return -1;
//标记是否遍历过
unordered_set<string>vis;
queue<string>q;
q.push(startGene);
vis.insert(startGene);
//记录次数
int ret=0;
while(!q.empty())
{
ret++;
int sz=q.size();
//同时扩展
while(sz--)
{
string s=q.front();
q.pop();
string change="ACGT";
//8个位置
for(int i=0;i<8;i++)
{
//每次只能变化一个位置
string tmp=s;
//4种变化
for(int j=0;j<4;j++)
{
tmp[i]=change[j];
if(tmp==endGene) return ret;
if(hash.count(tmp)&&!vis.count(tmp))
{
q.push(tmp);
vis.insert(tmp);
}
}
}
}
}
return -1;
}
};
- 单词接龙
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList)
{
unordered_set<string>hash(wordList.begin(),wordList.end());
unordered_set<string>vis;
//特殊处理
if(hash.count(endWord)==0) return 0;
int len=beginWord.size();
queue<string>q;
q.push(beginWord);
vis.insert(beginWord);
//记录次数,注意根据题目要求要从1开始
int ret=1;
while(!q.empty())
{
ret++;
int sz=q.size();
//同时扩展
while(sz--)
{
string s=q.front();
q.pop();
//一共len个字符
for(int i=0;i<len;i++)
{
string tmp=s;
//26个英文字母
for(int j=0;j<26;j++)
{
tmp[i]='a'+j;
if(tmp==endWord) return ret;
if(hash.count(tmp)&&!vis.count(tmp))
{
q.push(tmp);
vis.insert(tmp);
}
}
}
}
}
return 0;
}
};
675. 为高尔夫比赛砍树
题目解析
675. 为高尔夫比赛砍树
算法原理
1.我们通过对数组下标进行排序，确定砍树的先后顺序
2.两个树之间进行一个BFS，确定出最短路径，依次遍历即可
代码编写
class Solution {
public:
int m,n;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int cutOffTree(vector<vector<int>>& f)
{
m=f.size();
n=f[0].size();
//对数组下标进行排序
vector<pair<int,int>>tree;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(f[i][j]>1) tree.push_back({i,j});
}
}
sort(tree.begin(),tree.end(),[&](pair<int,int>p1,pair<int,int>p2)
{
return f[p1.first][p1.second]<f[p2.first][p2.second];
});
int fx=0;
int fy=0;
int sum=0;
//砍树
for(auto [fa,fb]:tree)
{
int step=bfs(f,fx,fy,fa,fb);
if(step==-1) return -1;
sum+=step;
fx=fa;
fy=fb;
}
return sum;
}
int bfs(vector<vector<int>>& f,int fx,int fy,int fa,int fb)
{
//起始位置和终止位置相同
if(fx==fa&&fy==fb) return 0;
queue<pair<int,int>>q;
int vis[m][n];
memset(vis,false,sizeof(vis));
q.push({fx,fy});
vis[fx][fy]=true;
int step=0;
while(!q.empty())
{
step++;
int sz=q.size();
while(sz--)
{
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&&f[x][y]>=1&&!vis[x][y])
{
if(x==fa&&y==fb) return step;
else
{
q.push({x,y});
vis[x][y]=true;
}
}
}
}
}
return -1;
}
};
二、多源最短路问题
多元BFS：用bfs解决边权为一的多源做短路问题。
如何解决：
1.暴力方法，把多源最短路问题转化成若干个单源最短路问题，但是这样会超时，时间复杂度太高。
2.把所有源点当成一个超级源点，问题就变成了单源最短路问题
代码编写：把所有起点加入到队列中，一层层扩展
542. 01 矩阵
题目解析
542. 01 矩阵
算法原理
我们本道题就是经典的多源最短路问题，我们按照题目要求把1当作起点，放入队列中，但是这样解题会很麻烦。
正难则反
我们可以把0加入到队列中，进行扩展
我们不需要用上面的step，vis数组等，
我们直接用一个dist数组表示距离就可以：
如果为-1表示没有遍历过；如果不为-1，就表示最短路径
代码编写
class Solution {
public:
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
vector<vector<int>> updateMatrix(vector<vector<int>>& mat)
{
//从所有0位置开始扩展
int m=mat.size();
int n=mat[0].size();
vector<vector<int>>dist(m,vector<int>(n,-1));
queue<pair<int,int>>q;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if(mat[i][j]==0)
{
q.push({i,j});
dist[i][j]=0;
}
//注意这里为社么可以
while(!q.empty())
{
auto [a,b]=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int y=b+dy[i]; int x=a+dx[i];
if(x>=0&&x<m&&y>=0&&y<n&&dist[x][y]==-1)
{
dist[x][y]=dist[a][b]+1;
q.push({x,y});
}
}
}
return dist;
}
};
1020. 飞地的数量
题目解析
1020. 飞地的数量
算法原理
我们结合上道题目，本道题的难点就是如何找到个数，这个直接求是很困难的
正难则反
因为边界上的块不能统计进最后的结果中，那我们就对边上的点进行·BFS遍历，最后遍历一遍数组，我们没有遍历过的并且值为1，就是我们需要返回的结果。
代码编写
我们这里遍历四条边有两种写法。
第二种很好写，不容易出错，但是时间复杂度高
class Solution {
public:
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int numEnclaves(vector<vector<int>>& grid)
{
queue<pair<int,int>>q;
int m=grid.size();
int n=grid[0].size();
vector<vector<bool>>vis(m,vector<bool>(n,false));
// 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 j=0;j<n;j++)
// {
// if(grid[0][j]==1)
// {
// q.push({0,j});
// vis[0][j]=true;
// }
// if(grid[m-1][j]==1)
// {
// q.push({m-1,j});
// vis[m-1][j]=true;
// }
// }
//遍历四条边
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(i==0||i==m-1||j==0||j==n-1)
{
if(grid[i][j]==1)
{
q.push({i,j});
vis[i][j]=true;
}
}
}
}
while(!q.empty())
{
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 total=0;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(grid[i][j]==1&&vis[i][j]==false)
{
total++;
}
}
}
return total;
}
};
总结
以上就是今天要讲的内容 。希望对大家的学习有所帮助，仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~ 😘 😘 😘