广度优先搜索

BFS 可视化

广度优先搜索（Breadth First Search）也称为宽度优先搜索，简称广搜或者 BFS，是遍历图存储结构的一种算法。

在之前的课程中，我们学习过深度优先搜索，不走回头路的搜索，深搜对于求最短路径问题比较困难，而广搜最广泛的应用就是求最短路径问题（如迷宫到达出口的最短路是多少）。

广搜和深搜最显著的区别就是，一个是一层一层走的，一个是一次性走到底。

在学习广搜之前，首先要了解广搜的核心——queue

queue 是C++STL中的一种容器，中文叫做队列。队列就像同学排队一样，来了一个新的人，只能放到后面去。因为队列的人可能太多了，你每次只能看到排在最前面的同学 ，只能让最前面的同学离开。

#include<queue>//对应的头文件
queue<int> que;//定义一个存储int类型的队列 名字叫 que
que.push(x);//在队列中加入一个数字
que.front();//返回队列最前面的数字
que.pop();//丢掉队列最前面的数字
que.size();//返回队列里的大小
que.empty();//返回布尔值，是否为空
//以上操作复杂度均为O(1)

//除此之外，que还能存两维的内容，如果要存坐标，可以使用 pair类型stl
queue<pair<int,int>> que
que.push({1,1});
pair<int,int> tmp = que.front();
int x= tmp.first;
int y= tmp.second;

任务一：将以下数字放入队列，并按顺序输出

7
8 7 1 3 4 2 1

任务二：将以下坐标(x,y)放入队列，并按顺序输出

5
1 2
4 5
6 3
2 3
3 3

广度优先搜索的流程

广度优先搜索

每次放入队列的节点都是目前离初始节点最近的，按照原来顺序出队列的时候，也保证是离初始节点从近到远，因此bfs遍历的过程符合最短的情况。

参考模板

单点

void bfs(int st){
    queue<int> que;
    que.push(st);//先放入初始节点
    for(int i=1;i<=n;i++) vis[i]=0;
    vis[st]=1;
    while(que.size()){//直到que为空为止
        int now = que.front();
        que.pop();//取出第一个节点
        for(){
            //遍历now节点能一步走到的所有节点
            int nex;//新节点记作nex
            if(vis[nex]) continue;//如果存过就不要了
            que.push(nex);//放入队列等待遍历
            vis[nex]=1;
        }
    }
}

二维坐标

int fx[4][2]={1,0,0,1,-1,0,0,-1};
void bfs(int sx,int sy){
    queue<pair<int,int>> que;
    que.push({sx,sy});//先放入初始节点
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) vis[i][j]=0;
    }
    vis[sx][sy]=1;
    while(que.size()){//直到que为空为止
        pair<int,int> tmp = que.front();
        que.pop();//取出第一个节点
        int nowx=tmp.first;
        int nowy=tmp.second;
        for(int i=0;i<4;i++){//遍历四个方向
            int nexx=nowx+fx[i][0];
            int nexy=nowy+fx[i][1];
            if(nexx<=0||nexx>n||nexy<=0||nexy>m) continue;
            //判断越界
            if(vis[nexx][nexy]) continue;
            //判断塞过
            que.push({nexx,nexy});
            vis[nexx][nexy]=1;
        }
    }
}