什么是广度优先搜索？

广度优先搜索（Breadth-First Search，简称BFS），是一种图遍历算法。它从给定的起始节点开始，逐层地向外扩展，先访问起始节点的相邻节点，然后再访问相邻节点的相邻节点，以此类推，直到遍历完所有可达节点。

搜索模板

首先我们需要一个队列来辅助BFS实现，还需要一个初始化的输入数组，还有一个标记数组。先找到BFS的起点跟终点，确定好之后，先把起点vis==true，把起点入队，然后进入BFS函数，进入BFS函数一般先是一个大while循环，来管理队列的入队、出队。

queue<type> Q;
Q.push(初始状态);//将初始状态入队
while(!Q.empty()){
    Type v=Q.front();//取出队首
    Q.pop();//出队
    for(枚举所有与v邻接的点){//找到v的所有可达状态
        if(是合法的){//w需要满足某些条件 
            Q.push(w);//入队 
        }
    } 
}

使用数组模拟队列

int head=1,tail=0;
void bfs(){
    tail++;//入队
    while(head<=tail){
        head++;//出队
        //扩展各种可能状态
        for(int i=1;i<=n;i++){
            if(越界) continue;
            if(访问过) continue;
            if(无效状态) continue;
            if(达到目标){
                //输出解
                return;
            }
            tail++;//添加新状态到末尾
        }
    }
}

queue<node> q;
void bfs(){
    while(!q.empty()){
        node tmp=q.front();//node为(x,y)结构体
        q.pop();//出队
        if(到达目标终点){
            更新
            return;
        }
        //周围的m个方向搜索
        for(int i=0;i<m;i++){//m个方向
            int dx=tmp.x+bx[i];
            int dy=tmp.y+by[i];
            if(下标越界){
                continue;
            }
            if(已经被标记过了){
                continue;
            }
            //否则就是合法的
            vis[dx][dy]=1;//先标记
            q.push(node{dx,dy});//再新点入队
        }
    }
}

使用场景

1、图的遍历问题

​ 迷宫问题，BFS题里面最简单的问题，直接利用BFS的思想遍历即可，判断是否能到达。

2、最短路问题

广搜可以理解为树的层次遍历，也就是说如果BFS搜索到了一个满足问题的答案，那么这个答案肯定是“距离最近的”，是“最内层的”，那么就不需要继续向外层搜索了，所以BFS比DFS更适合找最优解。

3、连通块问题