【算法】BFS 系列之边权为 1 的最短路问题
目录
一、算法简介
最短路问题是图论中一种经典的题型，包括单源最短路、多源最短路、边权为 1 的最短路等等。本篇主要讲述的是边权为 1 的最短路问题。
有如下一幅无向图，其中的每个点都可以看作是一个地点，两点之间的线可以看作是一条路径，路径上标识的权值（边权）可以看作是路径的长度，所谓最短路问题，就是求一个地点到另一个地点的最短路径长度。
而边权为 1 的最短路问题，就是指每条路径上的权值都为 1 或都相同。
对于这类问题，通常是借助 BFS，结合哈希表来得出一个最优解，其中，BFS 通过模拟一个队列的入队和出队来完成，而哈希表用来标识某一个地点是否已经遍历过。
之所以能用 BFS 得到最优解，是因为在入队和出队的过程中，一定会有一次层序遍历比另一次先到达某个地点。例如下图中，A到达E有两条路径，但由于边权为 1，A->C->E 一定比 A->B->D->E 更短，且由于 BFS 是层序遍历的，从 A 点同时出发，一层一层向外扩展的，因此 E 点一定和 D 点同时入队，此时 A->C->E 已经走完了，A->B->D->E 才走到 D 还没走到 E，因此在进行 BFS 时，是能够区分最短路径，能够找到最优解的。
而最短路径其实就是，从起点到终点进行 BFS 时所扩展的层数。
二、相关例题
1）迷宫中离入口最近的出口
.1- 题目解析
如果把小人最初所在的位置当作是一个地点，两个格子之间是一条长度为 1 的路径，那么这道题就可以抽象成是边权为 1 的最短路问题。
我们直接使用 BFS 遍历路径和地点即可。
.2- 代码编写
class Solution {
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
public:
int nearestExit(vector<vector<char>>& maze, vector<int>& e) {
int m=maze.size(),n=maze[0].size();
bool vis[m][n]; //记录地点是否被遍历过
memset(vis,0,sizeof(vis));
queue<pair<int,int>> q;//通过队列的入队和出队来实现BFS
q.push({e[0],e[1]});
vis[e[0]][e[1]]=true;
int step=0; //记录扩展的层数
while(q.size())
{
step++;//每次向外扩展一层都要记录
int sz=q.size();//每次取队长，方便出队
for(int i=0;i<sz;i++)
{
auto [a,b]=q.front();q.pop();
for(int j=0;j<4;j++)
{
int x=a+dx[j],y=b+dy[j];
if(x>=0 && x<m
&& y>=0 && y<n
&& maze[x][y]=='.' && !vis[x][y])
{
if( x==0 ||x==m-1 || y==0 || y==n-1) //扩展到矩阵边界，则可返回了
return step;
q.push({x,y});
vis[x][y]=true;
}
}
}
}
return -1;
}
};2）最小基因变化
.1- 题目解析
字符串 AAAA 可以变化成 CAAA、GAAA、TAAA 等等，如果将这些字符串看作是一个地点，那么由一个字符串变化成另一个字符串的过程，就可以抽象成是边权为 1 的最短路问题。
.2- 代码编写
class Solution {
public:
int minMutation(string startGene, string endGene, vector<string>& bank) {
unordered_set<string> vis;//标识已经搜索过的字符组合
unordered_set<string> hash(bank.begin(),bank.end());//标识基因库的字符组合
string change="ACGT";//标识可变化的字符
//处理边界情况
if(startGene==endGene) //变化前后相等
return 0;
if(!hash.count(endGene)) //基因库里不存在
return -1;
queue<string> q;
q.push(startGene);
vis.insert(startGene);
int ret=0;//记录扩展的层数
while(q.size())
{
ret++;
int sz=q.size();
while(sz--)
{
string t=q.front();
q.pop();
//暴力枚举所有可变的字符组合
for(int i=0;i<8;i++)//遍历原字符组合
{
string tmp=t;//细节问题
for(int j=0;j<4;j++)//遍历可变化的字符
{
tmp[i]=change[j];
if(hash.count(tmp)&&!vis.count(tmp))//当前枚举的一种字符组合在基因库中存在
{
if(tmp==endGene) //若已枚举出最终结果，则直接返回
return ret;
q.push(tmp); //否则继续BFS枚举字符组合
vis.insert(tmp);
}
}
}
}
}
return -1;
}
};3）单词接龙
.1- 题目解析
本题与上一道题几乎一模一样，也可以将符串看作是一个地点，将一个字符串变化成另一个字符串的过程抽象成是边权为 1 的最短路问题。
.2- 代码编写
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))return 0;
queue<string> q;
q.push(beginWord);
vis.insert(beginWord);
int ret=1;//统计一共有多少个单词
while(q.size())
{
ret++;
int sz=q.size();
while(sz--)
{
string t=q.front();
q.pop();
//暴力枚举所有可变化的字符组合
for(int i=0;i<t.size();i++)
{
string tmp=t;
for(char ch='a';ch<='z';ch++)
{
tmp[i]=ch;
if(hash.count(tmp) && !vis.count(tmp))
{
if(tmp==endWord)return ret;
q.push(tmp);
vis.insert(tmp);
}
}
}
}
}
return 0;
}
};4）为高尔夫比赛砍树
.1- 题目解析
先找出砍树的顺序，然后按照砍树的顺序，一个一个用 BFS 求出最短路即可。
.2- 代码编写
class Solution {
int m,n;
public:
int cutOffTree(vector<vector<int>>& forest) {
m=forest.size(),n=forest[0].size();
//找砍树的顺序
vector<pair<int,int>> trees;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(forest[i][j]>1)trees.push_back({i,j});
}
}
sort(trees.begin(),trees.end(),[&](const pair<int,int>& p1,const pair<int,int>& p2)
{
return forest[p1.first][p1.second]<forest[p2.first][p2.second];
});
//按顺序砍树
int bx=0,by=0;
int ret=0;
for(auto& [a,b]:trees)
{
int step=bfs(forest,bx,by,a,b);//找起始位置到终止位置的最短路径
if(step==-1)return -1;
ret+=step;
bx=a,by=b;//继续遍历下一个位置
}
return ret;
}
bool vis[51][51];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int bfs(vector<vector<int>>& forest,int bx,int by,int ex,int ey)
{
if(bx==ex && by==ey)return 0;//处理边界情况
queue<pair<int,int>> q;
memset(vis,0,sizeof(vis));//每次重新标识bfs
q.push({bx,by});
vis[bx][by]=true;
int step=0;
while(q.size())
{
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],y=b+dy[i];
if(x>=0 && x<m && y>=0 && y<n && forest[x][y] && !vis[x][y])
{
if(x==ex && y==ey)return step;
q.push({x,y});
vis[x][y]=true;
}
}
}
}
return -1;
}
};原文地址：https://blog.csdn.net/waluolandao/article/details/142351485
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！