bfs

BFS(广度优先搜索)

OIer在做题中,经常会遇到最短路径问题,连通块问题,迷宫问题等等…
那么我们应该如何处理这种题目呢

接下来给大家介绍BFS(广度优先搜索)

概念

如何理解广度优先搜索

(这里借用图码的概念图)

本质上 BFS 就是更大范围内搜索，先访问完当前顶点的所有邻接点, 之后如果下一个节点也有邻接点, 那么就接着往下搜索.

其实可以理解为 你每到一个分岔路口,就会出现几个朋友 , 帮助你去走这些分岔路. 或者理解为 “多线程” (当然只是方便理解,并不是真正意义上的多线程)

为了保证不重复,所以说我们每次走过的路 都被标记一下, 下次不去走他

广度优先搜索是图论中的一种算法, 他绝大多数是基于 队列(Queue) 实现的

在C++ 中 我们可以使用

#include <queue>

引入 STL 中的队列结构
这可以很好的帮助我们解决广搜问题

实际解决思路

当我们看到类似最短路径的问题, BFS是首选

#include <iostream>
#include <queue>
using namespace std;
#define MAXN 1000000

int xx[4] = {1,0,-1,0};
int yy[4] = {0,-1,0,1};

bool used[MAXN][MAXN];//这个数组用来存储我们是否走过某个点
int map[MAXN][MAXN];//这个是题目所给的样例地图
int main() {
    //...接收地图,宽高,内容
    //初始化used 建议memset 全部设置为false 或 0
    
    //我们使用 queue 创建一个x 和 y
    queue<int> x; queue<int> y; 
    x.push(0);y.push(0);//初始点放入队列中
    used[0][0] = true; //并标记为true

    while(!x.empty()) {//如果x不为空就一直搜
        for(int i = 0; i < 4; i++) {//每个方向开始搜索

            //邻接点新的坐标
            int 邻接点X坐标 = x.front() + xx[i];
            int 邻接点Y坐标 = y.front() + yy[i];

            if(一些逻辑 判断是否满足被填充的要求) {
                //满足要求 将这个点加到 队列中
                x.push(邻接点X坐标); y.push(邻接点Y坐标);
            }
        }
        x.pop();y.pop();//弹出当前的坐标,保证下次起始坐标是邻接点的坐标
    }
    return 0;
}

注意 其中 xx yy 是我们每次走的方向

int xx[4] = {1,0,-1,0};
int yy[4] = {0,-1,0,1};

OIer可以自定义方向,无需弄死

注意处理连通器问题时
我们需要新创建一个函数

void bfs(int x,int y){
    ......
}

这个函数中去编写BFS算法
在主函数中

int main() {

    //...其他处理
    for(int i = 0; i < 宽度; i++) {
        for(int j = 0; j < 高度; j++) {
            if(没被搜过,并且满足其他条件) bfs(i,j);
        }
    }


    return 0;
}

通常连通块问题解决的是连通块的个数 所以我们可以在if语句中 写入

if(没被搜过,并且满足其他条件){
    block++;
    bfs(i,j);
} 

坑

注意在判断是否超出宽高时
是 >= 或 <= 而不能写成 > 或 <
否则则会出现其他异常