当前位置：首页 > news >正文

图论算法篇：BFS宽度优先遍历

news 2025/2/25 16:23:45

在这里插入图片描述

那么bfs算法的大名想必大家都一定听闻过，那么也许有的人在认识我们bfs算法之前是先接触的我们的dfs算法，那么目前我们的算法世界中的两种搜索算法就是我们的dfs和我们的bfs，那么废话不多说，就让我们进入bfs算法的学习

BFS算法原理

那么在介绍我们BFS算法的原理之前，我们还是来先见一见我们BFS算法的一个应用场景吧，那么假设在一个图中，我们现在有一个起点和一个目标点，那么起点和目标点是不重合的，并且规定在这个图中起点到目标点一定有一条路径，那么现在我么要找到我们起点到目标点的最短路径。

那么看到这个场景，那么假设你现在还没学过BFS算法，那么你的思路会是什么，想必大部分人的常规思路就是我直接去枚举去遍历我们从当前位置到我们目标位置的所有路径，然后从中筛选出最短的那一条路径，那么采取的就是带路径的DFS实现，当然这个思路肯定是没有问题，但是我们最优秀的还是我们的BFS算法来解决这个问题。

那么我们DFS算法采取的手段是依次遍历从我们当前节点出发的每一条路径，而BFS采取的方式则是我们依次展开与我们当前起点直接相连的每一个节点，然后再逐步展开与刚才起点直接相连的节点的节点，逐渐向外扩充直到扩充到我们的目标点。

那么这个向外扩充的过程我们还是可以转换为遍历一棵多叉树，只不过这次遍历不再是我们的像我们DFS那样的前序遍历我们的多叉树，而是采取的是层序遍历的方式遍历我们的多叉树，那么我们的根节点就是我们的起点，那么我们根节点下面的一层分支也就是第一层的孩子节点就是与我们起点直接相连的节点，同理那么我们第二层的孩子节点就是我们第一层所对应节点直接相连的节点，那么我们的BFS就是一层一层的往下遍历，每一层遍历完之后，再展开之后的一层，然后接着再重复之前的过程，那么最终会将我们的目标节点添加到我们的这棵多叉树当中，一旦添加到我们的目标节点，那么此时我们多叉树的层数就是最短路径的步数
在这里插入图片描述

那么想必你看到这里，我相信你一定会有一个疑问：

那么就是我们这个BFS过程为什么就能够做到一旦将目标节点添加到我们的多叉树当中，那么该多叉树的高度就是我们的最短路径长度呢？

那么要回答这个问题，那么我们就得理解我们BFS过程的具体细节，那么我们BFS每次往外扩充的时候，我们先是从起点往外扩充，并且扩充的都是与该节点直接相连的节点，那么该扩充的节点一定是距离当前起点最近的节点，因为扩充的都是直接相连的节点

那么这个过程，就可以形象的来打个比方，就好比于我们往平静的湖面上抛了一颗石子，那么这个石子抛的落点就是我们的起点，那么接下来我们的湖面就会产生以该石子的落点为圆心且半径为0以及半径为1的圆的水波然后往外扩充，那么我们知道在圆弧上的圆与我们的圆心的连线它一定是直线的，而不是什么所谓的弯曲的曲线，而在圆弧上的每个点到我们圆心的最短距离就是我们的半径，而这里我们圆弧上的点就是我们刚才的例子中依次与起点直接或者间接相连的一个个节点，那么一旦我们的圆弧扩展到我们的目标节点，那么我们圆心到我们目标节点的半径就是最短距离，而这个半径就是我们上文所说的多叉树的高度
在这里插入图片描述

那么知道了我们BFS的原理之后，那么接下来的问题就是如何实现我们的BFS，那么我们刚才上文说了，我们的BFS就是一个层序遍历的二叉树模型，所以实现我们的BFS就是用一个队列来实现，那么我们将我们当前的节点压入到我们的队列中，由于最开始只有一个起点，那么我们就只需要将起点压入到队列当中，然后用一个size变量记录当前队列的节点数量，并且我们还有一个level变量记录当前在队列中的节点在多叉树中所处的高度，而之后我们会依次弹出我们队列当中的节点，那么我们每弹出一个节点，那么我们就要将该节点直接相连的节点压入到我们的队列中，需要弹出size次，弹完之后再重新计算一下我们队列的中的节点的个数，然后高度加一，接着重复之前的步骤，直到目标节点压入队列当中，那么此时的level值就是我们要求的答案。

注：这里我们还要准备一个bool类型的数组，我们之前被访问过的节点不应该在添加到下一层当中去，所以我们每次添加一个节点，我们都需要检查一下该节点所对应的bool类型的数组

BFS代码板子：

//我采取的建图是链式前向星的方式来给的BFS的代码板子
int bfs(vector<int>& head, vector<int>& next, vector<int>& to, queue<int>& q, int start, int target,vector<bool> check) {q.push(start);  // 将起点压入队列int level = 0;  // 初始化层数（路径长度）while (!q.empty()) {int size = q.size();  // 当前层的节点数量while (size--) {int h = q.front();  // 获取队头节点q.pop();  // 弹出队头节点int m = head[h];  // 获取与节点h相连的第一条边while (m != -1) {  // 遍历所有与节点h相连的边if (to[m] == target) {  // 如果目标点被访问return level;  // 返回当前层数（路径长度）}if(check[to[m]]!=false)//检查当前节点是否被访问过q.push(to[m]);  // 将目标点压入队列m = next[m];  // 移动到下一条边}}level++;  // 增加层数（路径长度）}return -1;  // 如果目标点不可达，返回-1
}

注：我们的BFS的寻找的最短路径的应用场景，只能是针对的是边的权值为1的情况，一旦有权值为负的边或者权值大于1的边出现，那么我们只能用我们的迪杰斯特拉算法来实现，这在我之后的文章中会讲解

那么原理以及代码方面的实现掌握了，那么接下来就是如何用我们的算法来来解题应用了

BFS应用

题目一：最短路径

题目：我们现在有一个矩阵，那么矩阵当中的元素值不是0就是1，那么现在我们要在矩阵为1的位置作为起点到达另一个与该位置不重合的目标点上去，那么我们只能在为一的元素上移动，题目保证一定会存在一条给定的起始点与目标点的一条路径，那么问我们起始点到达目标点的最短路径长度是多少？

题目思路：那么这道题就是我们BFS的一个板子题，那么我们就是直接上手我们的BFS就行了，这题就是考察BFS代码的熟悉度，这是一道单源BFS的题

代码实现：

class Solution {
public:// 节点结构体，用于存储坐标struct Node {int x, y;};int shortestPath(std::vector<std::vector<int>>& graph,int startx,int starty,int endx,int endy) {int rows = graph.size();int cols = graph[0].size();std::vector<std::vector<bool>> visited(rows, std::vector<bool>(cols, false));std::queue<Node> q;visited[startx][starty]=true;q.emplace(startx,starty);int level = 0;int expend=0;// BFS 遍历while (!q.empty()) {int size = q.size();while (size--) {Node current = q.front();q.pop();int fx = current.x;int fy = current.y;// 检查四个方向if (fx - 1 >= 0 && graph[fx - 1][fy] == 1 && !visited[fx - 1][fy]) {if(fx-1==endx&&fy==endy){return level}q.emplace(fx - 1, fy);visited[fx - 1][fy] = true;expend=1;}if (fy - 1 >= 0 && graph[fx][fy - 1] == 1 && !visited[fx][fy - 1]) {if(fx==endx&&fy-1==endy){return level}q.emplace(fx, fy - 1);visited[fx][fy - 1] = true;expend=1;}if (fx + 1 < rows && graph[fx + 1][fy] == 1 && !visited[fx + 1][fy]) {if(fx+1==endx&&fy==endy){return level}q.emplace(fx + 1, fy);visited[fx + 1][fy] = true;expend=1;}if (fy + 1 < cols && graph[fx][fy + 1] == 1 && !visited[fx][fy + 1]) {if(fx==endx&&fy+1==endy){return level}q.emplace(fx, fy + 1);visited[fx][fy + 1] = true;expend=1;}}if(expend)level++;expend=0;}}// 如果没有找到路径，返回 -1（按题目保证，这不应发生）return -1;}
};

注：这里我们的BFS的while循环中，我们每一次弹出节点后增加的高度一定是我们有新的节点加入，如果我们节点都弹出了，但是没有新的节点加入的话，那么此时不用增加我们的level。

题目二：岛屿

题目：现在我们有一个矩阵，那么这个矩阵中的元素值只有0和1这两种，那么其中我们元素0的位置代表海洋，而元素1的位置则代表陆地，那么现在我们要寻找每个海洋离自己最近陆地的距离的最大值，其中距离的就算则是按照哈夫曼距离计算，即：|x0-x1|+|y0-y1|,返回这个距离

题目思路：那么现在我们要求每一个海洋离自己最近的陆地的距离的最大值，那么我们常规的思路就是单源BFS，我们去枚举每一个海洋离自己最近的陆地的距离，然后再综合筛选得到最大的距离，那么其中枚举每一个海洋离自己最近的陆地的距离的话，我们就对该位置的海洋进行BFS，直到扩充到有1，那么就进行结算，但是我们分析一下这个思路，如果说我们这个矩阵特别大，并且海洋的数量很多的话，那么对每一个海洋进行BFS的枚举代价肯定就很大，所以这道题我们不能按照这个思路来就解决这个问题，我们得换一种思路。

BFS的思路肯定是没错的，但是这里我们进行BFS的对象不是以海洋为中心，而是以我们的陆地为中心，并且这里我们是多个陆地同时进行一个BFS，也就是多源BFS，那么对于多源BFS，也就是我们每一个陆地同时往外展开扩充，那么每一次往外扩充，那么每一个源头扩充到的海洋，那么对于海洋来说，此时如果他在被某个源头的海洋给扩充到了，并且是第一次被访问到，那么说明该源头一定是离他最近的陆地。

那么这就要说一下这里多源BFS的一个细节了，那么对于多源BFS来说，相比于单源BFS来说，那么它最大的不同就是多个源头同时往外扩充，那么这就出现一种情况，那么我们的某个位置可能在不同的时刻下，被不同的源头给扩充访问到，但是对于该位置来说，那么它第一次被访问被扩充到，那么访问到该位置的源头一定是距离它最近的一个源头，即使它在之后的时刻被其他源头给访问到了，就好比于我们用多个不同位置的雷达探测一个位置，那么该位置第一次被其中一个雷达的声波给探测到了然后返回该声波给雷达，那么之后的时刻可能还被其他位置的雷达的声波给探测到，再次返回，那么对于该位置来说，离它最近的雷达一定是它第一次接收到声波然后返回的那个雷达，因为我们的雷达是同时发射我们的声波，而我们每个雷达发送声波的速度是一样的，那么我们该位置第一次接收到其中一个雷达发送到的声波，那么意味着该雷达发送声波到达该位置的时间相比于其他位置的雷达来说是最短的，而路程等于速度乘以时间，那么速度一样，时间越短，那么路程越小，那么也就证明了第一次访问到该位置的雷达一定是离该位置最近的雷达。

所以这就是我们多源BFS要梳理的一个重要细节，那么我们确实会出现同一个位置在不同的时刻被其他源头给访问到，但是对于该位置来说，我们只关心第一次被访问的那个源头是谁，那么第一次被访问到的源头就是离它最近的陆地，那么该源头往外扩充的层数就是该位置距离最近陆地的距离，所以这里在实现我们的BFS的时候，我们要准备一个bool类型的一个数组用来检查当前位置的海洋是否被访问过，如果被访问过，那么我们该源头就不用将其扩充。

那么由于我们是对个源头同时进行BFS，那么此时我们我们会用一个队列和一个level来记录当前每个源头距离它最近leave距离的海洋，那么直到我们队列不能在往外扩充的时候，那么此时的level就是我们要的答案。

代码实现：

class Solution {
public:class Node {public:int x;int y;Node(int x_val, int y_val) : x(x_val), y(y_val) {}};int minlength(std::vector<std::vector<int>>& graph) {std::vector<Node> l1;// 收集所有值为 1 的节点for (int i = 0; i < graph.size(); i++) {for (int j = 0; j < graph[0].size(); j++) {if (graph[i][j] == 1) {l1.emplace_back(i, j);}}}std::queue<Node> l2;// 将所有值为 1 的节点入队for (const auto& node : l1) {l2.push(node);}std::vector<std::vector<bool>> check(graph.size(), std::vector<bool>(graph[0].size(), false));// 标记所有值为 1 的节点为已访问for (const auto& node : l1) {check[node.x][node.y] = true;}int level = 0;int expend=0;// BFS 遍历while (!l2.empty()) {int size = l2.size();while (size--) {int fx = l2.front().x;int fy = l2.front().y;l2.pop();// 检查四个方向if (fx - 1 >= 0) {if (graph[fx - 1][fy] == 0 && !check[fx - 1][fy]) {l2.emplace(fx - 1, fy);expend=1;check[fx - 1][fy] = true;}}if (fy - 1 >= 0) {if (graph[fx][fy - 1] == 0 && !check[fx][fy - 1]) {l2.emplace(fx, fy - 1);expend=1;check[fx][fy - 1] = true;}}if (fx + 1 < graph.size()) {if (graph[fx + 1][fy] == 0 && !check[fx + 1][fy]) {expend=1;l2.emplace(fx + 1, fy);check[fx + 1][fy] = true;}}if (fy + 1 < graph[0].size()) {if (graph[fx][fy + 1] == 0 && !check[fx][fy + 1]) {expend=1;l2.emplace(fx, fy + 1);check[fx][fy + 1] = true;}}}if(expend)level++;expend=0;}return level - 1;  // 减去 1，因为最后一次循环是多余的}
};