BFS算法详解：如何解决边权为1的最短路径问题
BFS算法详解：如何解决边权为1的最短路径问题
BFS（广度优先搜索）是一种常用算法，特别适合解决边权为1的最短路径问题。本文将通过理论讲解和具体题目实践，帮助读者深入理解BFS算法在最短路径问题中的应用。
BFS 解决最短路径问题
1. 最短路径问题简介
最短路径问题是图论里面最重要的问题，它包括单源最短路、多元最短路、边权为1的最短路、带负环的最短路等等。这里我们只讨论边权为1的最短路径问题。
边权为1的最短路径问题可以理解为：有一些地区，地区之间有道路相连，给定一个起点，问到达另一个点最短的路径是多少？
边上面可能赋予权值，权值可以理解为两个点之间的长度。当边权都相同时，问题就简化为边权为1的最短路径问题。
这类最短路问题的解决方案特别简单：从起点开始，进行一次BFS即可。
2. 迷宫中离入口最近的出口
题目链接：1926. 迷宫中离入口最近的出口
题目分析：
给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 ‘.’ 表示）和墙（用 ‘+’ 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列，你可以上下左右四个方向移动，让你找到离你刚开始所在位置最近的出口并且返回路径。这里的出口就是在maze边界上的空格子。注意刚开始的位置即使就是在maze边界上的空格子上也不能算作出口。如果不存在路径返回-1.
算法原理：
以第一个例子为例，刚开始这个小人可以向上走也可以向左走，如果把小人抽象成点的话，此时把点连成线，会发现每次都只走一步。会发现权值都是1，所以这个问题就可以转换成 边权为1的最短路径问题。从开始点出发到边界上的点最短路径是多少。
边权为 1 的最短路径问题
解法：BFS
如何解决前面已经说的非常详细了。把刚开始位置加入队列，然后一层一层往外扩，直到扩展到边界上的点为止。返回扩展的层数即可。注意还要搞一个二维数组用来标记当前为止是否已经被访问过了。
class Solution {
bool vis[101][101]={0};
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();
queue<pair<int,int>> q;
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 k = 0; k < 4; ++k)
{
int x = a + dx[k], y = b + dy[k];
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;//层序遍历结束之后还没有找到出口,返回-1
}
};
3. 最小基因变化
题目链接：433. 最小基因变化
题目分析：
基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是’A’、‘C’、‘G’ 和 ‘T’ 之一。求从基因序列 start 变为 end 所发生的有效的基因变化并且是最小的。有效的基因变化指的是start每次基因变化如果都是在基因库 bank 里就是有效的。一次基因变化就意味着这个基因序列中的一个字符发生了变化。例如，“AACCGGTT” --> “AACCGGTA” 就是一次基因变化。
算法原理：
先把这到题转为为之前遇到的关于图论问题中的，边权为 1 的最短路径问题。
给一个起始的基因序列，给一个终止的基因序列，想把这个起始基因序列转化为终止的基因序列。在转化过程中要求每次转化只能改变基因序列中其中一个字符并且只能从"A",“C”,“G”,"T"中任取一个字符。
如果把一个一个字符串抽象出图论中一个个点，那这个问题不就变成了，给一个起始位置和一个终止位置，中间有一些变化的的过程，问起始位置到终点位置最短路径是多少，这问题不就完美的抽象成图论问题吗。并且每次都是一步变化，因此就转变成边权为 1 的最短路径问题。
接下来就是细节问题：
肯定要创建一个队列，队列里存的是一个个字符串。而且还需要一个东西来标记当前字符串已经被搜索过了。原因是CAAA 继续向外扩展会回到AAAA这就有问题了，因此需要标记字符串已经被搜索。这里不能在用数组了，我们用hash表存一个个字符串。
用哈希表来标记搜索过的状态
如何枚举出当前这一次所有变化情况呢？
很简单搞一个for循环，对字符串中每一个字符遍历依次，并且每一个字符都按顺序修改成"A",“C”,“G”,“T”。这样就枚举出当前这一次所有变化情况。遍历字符串中每一个位置然后每一个位置都修改四次！而且因为我们前面有哈希表标记搜索过的状态因此不会有重复的情况，不用在判断一次当前字符串和前面字符串是否相等在修改，如 CAAA -> AAAA，因为AAAA已经被标记过搜索了，所以不用特殊判断。枚举出来的所有情况，都需要加入到队列里面吗？
并不需要，只需要把枚举出来并且在基因库bank里面的才加入到队列。如何快速判断是否在基因库中存在
把基因库中的字符串加入到hash表。此时枚举出来的字符串就可以在这个hash表找一下就可以。
class Solution {
public:
int minMutation(string startGene, string endGene, vector<string>& bank) {
unordered_set<string> hash(bank.begin(),bank.end());// 存储基因库里面的基因序列
unordered_set<string> vis; // ⽤来标记已经搜索过的状态
if(startGene == endGene) return 0;
if(!hash.count(endGene)) return -1;
queue<string> q;
q.push(startGene);
vis.insert(startGene);
int step = 0;
string change = "ACGT";
while(q.size())
{
step++;
int n = q.size();
while(n--)
{
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 step;
q.push(tmp);
vis.insert(tmp);
}
}
}
}
}
return -1;
}
};
4. 单词接龙
题目链接：127. 单词接龙
题目分析：
给一个起始单词给一个终止单词求起始单词转化为终止单词最短转换序列 中的 单词数目。如果不存在这样的转换序列，返回 0 。这道题和上面几乎是一模一样，唯一不一样的就是求得是最短转换序列 中的 单词数目。转化规则还是每次遍历字符串中每一个位置，每一个位置都可以 从 ‘a’~‘z’ 中按照顺序改变，但是不是盲目改变，改变之后得字符串必须在wordList字典中存在才行。才属于一次有效改变。
算法原理：
和最小基因序列几乎一模一样，不过就换成了每个位置从 ‘a’ ~ ‘z’ 中选，而且最终返回的是最短转换序列 中的 单词数目，因此第一个进入队列的也要算上。
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 n = q.size();
while(n--)
{
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;
}
};
5. 为高尔夫比赛砍树
题目链接：675. 为高尔夫比赛砍树
题目分析：
给一个mxn的矩阵，
0 表示障碍，无法触碰
1 表示地面，可以行走
比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度
每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。
你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。
算法原理：
当我们把题意搞清楚，我们知道砍树不能随便砍，必须按照从底到高顺序来砍，因此我们必须先想办法把下标中的树先按照从低到高排下序，然后从(0,0)开始砍。此时这个问题就转化为，1->2 只要知道1->2最短距离不就可以了吗，然后就可以砍2号树。在然后从 2->4，只要知道2->4最短距离然后就可以砍4号树。。。。 这不就变成了若干个迷宫问题了吗。然后把所有最短距离加起来就行了。
那如何先对树进行一下排序把砍树的顺序找到呢？
可以先用数组把所有待砍树的下标保存起来，然后根据下标所对应的值对下标进行排序。
class Solution {
int m,n;
public:
int cutOffTree(vector<vector<int>>& f)
{
m = f.size(), n = f[0].size();
// 1. 准备⼯作：找出砍树的顺序
vector<pair<int, int>> trees;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(f[i][j] > 1) trees.push_back({i, j});
sort(trees.begin(), trees.end(), [&](const pair<int, int>& p1, const pair<int, int>& p2)
{
return f[p1.first][p1.second] < f[p2.first][p2.second];
});
// 2. 按照顺序砍树
int bx = 0, by = 0;
int ret = 0;
for(auto& [a, b] : trees)
{
int step = bfs(f, 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>>& f, 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); // 清空之前的数据
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 && f[x][y] && !vis[x][y])
{
if(x == ex && y == ey) return step;
q.push({x, y});
vis[x][y] = true;
}
}
}
}
return -1;
}
}