【经典算法】BFS_最短路问题

1. 最短路问题介绍

最短路径问题是图论中的一类十分重要的问题。本篇文章只介绍边权为1(或边权相同)的最简单的最短路径问题。所谓边权，就是两点之间的距离。

这类问题通俗的说就是告诉你起点和终点，要你找出最短的路径或是最短路径是多少。

解决方法：从起点开始，来一次bfs即可。
A出队列后，向外扩展一层，B，C入队列，注意，此时出队列要B，C同时出(其实是写一个for循环，先B后C)。

那如何计算出最短路径是多少呢？
扩展的层数，就是最短路的长度。

2. 算法原理和代码实现(含题目链接)

1926.迷宫中离入口最近的出口

算法原理：
我们可以从起点开始层序遍历，并且在遍历的过程中记录当前遍历的层数。这样就能在找到出⼝的时候，得到起点到出⼝的最短距离。

把题目抽象为：从当前位置出发，到离边界上的那个点的最短路程是多少。

细节/技巧问题：

(1) 人当前所在位置不能当做出口。
(2) 出口：与边界相邻的空格就是出口。
(3) 人在移动时仅需走到出口位置即可，不需要走出迷宫。

代码实现：

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;q.push({e[0], e[1]});vis[e[0]][e[1]] = true;int step = 0; // 记录步数while(q.size()){step++;int sz = q.size();// 假设进去sz个，要同时出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;else{q.push({x, y});vis[x][y] = true;}}}}}return -1;}
};

433.最小基因变化

算法原理：

如果将每次字符串的变换抽象成图中的两个点和⼀条边的话，问题就变成了边权为1的最短路题。

其他细节/技巧问题：

(1) 原字符串每个字符变化后一定存在相同的，此时要用哈希表来标记搜索的状态，每次变化后都扔进哈希表中。
(2) 如何枚举出所有的变化情况呢？直接两层for循环。
(3) 变化成哪种字符串才能入队列呢？变化后的字符串在基因库中存在时，才队列。所以把基因库里的字符串扔进哈希表中，每次变化后都要判断是否在基因库中。

代码实现：

class Solution 
{
public:int minMutation(string startGene, string endGene, vector<string>& bank) {unordered_set<string> vis; // 记录字符串是否搜索过 unordered_set<string> hash(bank.begin(), bank.end()); // 判断变化后的字符串是否在库中//处理特殊情况if(startGene == endGene) return 0;if(!hash.count(endGene)) return -1;queue<string> q;q.push(startGene);vis.insert(startGene);string change = "AGCT";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);vis.insert(tmp);}}}}}return -1;}
};

127.单词接龙

算法原理：

这道题和第二题基本一模一样，都是把一个字符串变化成目标字符串，唯一不同的是本题统计的是整个过程中单词的个数，其实就是上一题的最小次数+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(beginWord == endWord) return 1;if(!hash.count(endWord)) return 0;queue<string> q;q.push(beginWord);vis.insert(beginWord);int ret = 0;while(q.size()){ret++;int sz = q.size();while(sz--){string t = q.front();q.pop();for(int i = 0; i < 10; i++){string tmp = t;for(char ch = 'a'; ch <= 'z'; ch++){tmp[i] = ch; // 每次只修改一个字符// 存在列表中并且没有被访问过if(!vis.count(tmp) && hash.count(tmp)){if(tmp == endWord) return ret+1; q.push(tmp);vis.insert(tmp);}}}}}return 0;}
};

675.为高尔夫比赛砍树

算法原理：

这道题目确实很难。
这道题可以抽象成若干个迷宫问题。我们只要计算出从这一棵树到下一棵树的最少步数，再把所有的步数相加，就可以求出砍完所有树的最少步数。所以这里要多次使用bfs算法，写成函数，它的作用是统计两棵树之间的最少步数。

难点/细节/技巧问题：

(1) 树的坐标如何存储。使用vector容器。
(2) 由于要按照高度从低到高开始砍，所以先要把树的高度排升序。
(3) bfs的参数是传起点和终点。

代码实现：

class Solution 
{int m, n;int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};public:int cutOffTree(vector<vector<int>>& f) {m = f.size(), n = f[0].size();// 记录树的位置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];});int bx = 0, by = 0; // 起始位置int step = 0;for(auto& [a,b] : trees){// 使用bfs计算两树之间的最短路int ret = bfs(f, bx, by, a, b);if(ret == -1) return -1;step += ret;bx = a, by = b; // 更新下一个位置的坐标}return step;}bool vis[51][51];int bfs(vector<vector<int>>& f, int bx, int by, int ex, int ey){if(bx == ex && by == ey) return 0;memset(vis, 0, sizeof(vis)); // 每次计算都要把标记还原queue<pair<int ,int>> q;q.push({bx, by});vis[bx][by] = true;int ret = 0; // 记录每两颗树之间的最短步数while(q.size()){ret++;int sz = q.size();while(sz--){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 && !vis[x][y] && f[x][y]){// 判断是否走到终点if(x == ex && y == ey) return ret;q.push({x, y});vis[x][y] = true;}}}}return -1;}
};

3. 算法总结

bfs算法是解决最短路问题的经典方法。我感觉解决最短路问题核心的关键是每一次出队列时都要把上一次入队列的数据全部出完(就要写for循环)，而最短路程就是向外扩展的层数。