【搜索回溯算法】：BFS的魔力--如何使用广度优先搜索找到最短路径

✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：搜索回溯算法篇–CSDN博客

在这里插入图片描述

文章目录

一.广度优先搜索（BFS）解决最短路问题
- 1.基本思想
- 2.算法步骤
二.例题
- 1.迷宫中离入口最近的出口
- 2.为高尔夫比赛砍树
- 3.最小基因变化
- 4.单词接龙

一.广度优先搜索（BFS）解决最短路问题

1.基本思想

广度优先搜索是一种图（或树）的遍历算法。在解决边权相等的最短问题时，他从起始节点开始，逐层的向外扩展搜索。
因为边权相等，所以先被搜索到的节点一定是通过最少的边到达的。

2.算法步骤

初始化
- 将起始节点标记为已访问，并将其加入到队列中。
- 记录起始节点到自身的距离为0。
搜索过程
- 取出队列头部节点
- 遍历该节点所有未访问的相邻节点
- 对于相邻节点，标记为已访问，并将其加入到队列中，然后距离加一。
- 重复上述操作，直到队列为空，或者找到目标节点。

在这里插入图片描述

二.例题

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

题目：

在这里插入图片描述

算法原理：

广度搜索，最短路的经典例题，给定迷宫中的起始位置，找到距离出口的最近距离，也就是离开迷宫的最短路径长度。

本道题就是棋盘格式，在二维数组中搜索，所以每一个位置都有上下左右四个方向可以搜索，但是不能越界，具体的搜索方式和上面图中的样例相同。

代码实现：

//重命名
typedef pair<int, int> PII;
//两个数组用来四个方向搜索
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};int nearestExit(vector<vector<char>>& maze, vector<int>& entrance){//获取行数和列数int m = maze.size(), n = maze[0].size();//创建一个布尔类型的二维数组vector<vector<bool>> check(m, vector<bool>(n));//创建一个队列，存放的是数组的下标queue<PII> q;//将起始位置入队，并标记为已遍历q.push({entrance[0], entrance[1]});check[entrance[0]][entrance[1]] = true;int step = 0;while(!q.empty()){//每一次外层循环，表示向外扩展一层，层数就是步数，所以步数加一step++;//获取当前层有多少个下标，依次出队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&&maze[x][y]=='.'&&check[x][y]==false){//如果符合入队条件并且是出口时，直接返回当前步数if(x==0||x==m-1||y==0||y==n-1){return step;}//如果符合入队条件但不是出口时，入队并标记为已遍历else{q.push({x, y});check[x][y] = true;}}}}}//如果循环结束也没找到出口，说明不存在出口return -1;
}

2.为高尔夫比赛砍树

题目：

! 在这里插入图片描述

算法原理：

因为力扣官方给的示例不是很好，没有完整的描述题目中的规则，所以这里没有展示官方示例，在下面图片中，我会先写一个示例来讲解本道题的题意，然后再写算法原理。本道题可以理解为上面的那道题的扩展，不再局限于一个起始位置和终点位置搜索

在这里插入图片描述

以图中的为例，既然要找到砍树所有树的最少步数，而砍树的顺序是固定的，所以只能限制每一次移动到下一个树时，必须是最短的路径，这不就转换成迷宫问题吗，以上面的砍树顺序为例，先从1到2，最短路径就是1->8->2，最少步数是2，再从2到4，最短路径就是2->8->4或者2->10->4，最少步数就是2，依次类推，将每一次的最少步数累加到一起，就是整个的最少步数。如果出现某个位置到某个位置不能到达时，比如有障碍不能通过，直接返回-1，因为出现某个树不能被砍掉，即使前面的步数再少，也不能砍完所有的树。

代码实现：

//重命名
typedef pair<int, int> PII;
//两个数组用来四个方向搜索
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int m = 0;
int n = 0;int bfs(vector<vector<int>>& forest,int bx,int by,int ex,int ey){//如果起始位置就等于终点位置返回0if(bx==ex&&by==ey){return 0;}//初始化布尔类型的二维数组，用来标记已遍历的位置vector<vector<bool>> check(m, vector<bool>(n));//创建一个队列，将起始位置入队queue<PII> q;q.push({bx, by});check[bx][by] = true;int ret = 0;while(!q.empty()){ret++;int sz = q.size();while(sz--){//先获取队头元素auto [i, j] = q.front();q.pop();for (int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x>=0&&x<m&&y>=0&&y<n&&forest[x][y]!=0&&check[x][y]==false){if(x==ex&&y==ey){return ret;}else{q.push({x, y});check[x][y] = true;}}}}}return -1;
}
int cutOffTree(vector<vector<int>>& forest){//获取行数和列数m = forest.size();n = forest[0].size();//新建立一个数组，用来存放每个位置的下标vector<PII> trees;//遍历整个原始数组，将大于等于1的位置存放到新数组中for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if(forest[i][j]>1){trees.push_back({i, j});}}}//按照原数组位置对应的值进行从小到大排序//使用Lambda表达式自定义排序规则，[&]是捕获列表，可以访问forest变量，()内是参数列表，{}内是函数体定义比较规则sort(trees.begin(), trees.end(), [&](const PII &p1, const PII &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);//如果返回的最短步数是-1，说明无法从当前起始位置到终点位置，直接输出-1if(step==-1){return -1;}//如果返回的不是-1，说明找到最短步数，累加ret += step;//将当前的终点位置作为下一个的起始位置bx = a, by = b;}return ret;
}

3.最小基因变化

题目：

在这里插入图片描述

算法原理：

本道题刚开始看可能觉得没有什么思路，但这也是最短路最经典的一个例题，虽然不是棋盘格式的搜索，但是根据题意我们可以自己写出搜索展开图，画出搜索展开图后就能明白为什么是最短路问题以及为什么可以用广度搜索来解。

在这里插入图片描述

本道题有两个细节要处理，一个是如何判断变化后的基因是否重复出现，一个是变化后的基因是否存在与基因库中；

因为基因序列是用字符串的形式表示，所以对于这两个细节的处理都可以借助哈希表来实现。

一个哈希表check用来存放每次变化后的基因，如果存放前发现哈希表中已经存在该变化后的基因，说明重复出现，不再添加到哈希表中。

另一个哈希表hash用来存放基因库中的基因序列，先遍历整个基因库，将所有基因序列存放到哈希表中，题中要求变化后的基因必须存在于基因库中才是有效的基因序列，所以变化后的基因在存放到另一个哈希表前，先判断是否存在基因库中，如果不存在该基因库中就不再添加，存在就继续存放，同时要判断是否重复出现。

搜索的实现方式还是和上面的格式一样，借助队列来实现，循环逐层搜索，直到找到目标基因序列。

代码实现：

int minMutation(string startGene, string endGene, vector<string>& bank){//建立两个哈希表，一个用来存放变化后的基因，防止相同的基因重复查找//一个用来存放基因库中的基因unordered_set<string> check;unordered_set<string> hash(bank.begin(), bank.end());//判断特殊情况，变化前基因等于变化后要查找的基因，直接返回0次if(startGene==endGene){return 0;}//如果变化后要查找的基因不在基因库中，直接返回-1if(hash.count(endGene)==0){return -1;}//建立一个队列,将变化前的基因入队，并存放到检查哈希表中queue<string> q;q.push(startGene);check.insert(startGene);string change = "ACGT";int ret = 0;while(!q.empty()){//每循环一次，相当与向外扩展一层，变化次数加一ret++;int sz = q.size();while(sz--){string t=q.front();q.pop();//i循环表示一个基因8个位置的变化，j循环表示一个位置有4种情况变化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)!=0&&check.count(tmp)==0){//如果满足上面两个条件并且就是结束字符串，直接返回当前变化次数if(tmp==endGene){return ret;}//如果不是结束字符串，入队，并且存放到检查哈希表中else{q.push(tmp);check.insert(tmp);}}}}}}//循环结束后还没有返回，说明没有找到结束字符串，返回-1return -1;
}

4.单词接龙

题目：

在这里插入图片描述

算法原理：

本道题可以说和上面的那道题最小基因变化一模一样，连代码过程几乎都是一样的，唯一有点不同的就是，上面那道题中一个位置只有四个字符可以变化，而本道题中一个位置有26个字符可以变化，所以在循环时对这点的处理不同，其他地方都是一模一样，所以上面那道题理解之后，本道题就会变得非常简单。

代码实现：

int ladderLength(string beginWord, string endWord, vector<string>& wordList){//和上一道题基因变化一样unordered_set<string> check;unordered_set<string> hash(wordList.begin(), wordList.end());if(beginWord==endWord){return 2;}if(hash.count(endWord)==0){return 0;}queue<string> q;q.push(beginWord);check.insert(beginWord);int ret = 1;while(!q.empty()){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)!=0&&check.count(tmp)==0){if(tmp==endWord){return ret;}else{q.push(tmp);check.insert(tmp);}}}}}}return 0;
}