广度优先搜索（BFS）

1.什么是广度优先搜索

百度对它的定义是这样的：宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

我们给出进一步的解释：它是从给定的起始节点开始，逐层地向外扩展，先访问起始节点的相邻节点，再访问相邻节点的相邻节点，直到遍历完所有可达节点。这一点与DFS的一条路走到黑有着明显区别。

图例如下：

第一层遍历

第二层遍历

2.如何实现

具体BFS算法如下：

1.创建一个队列，并将起始节点入队；

2.将起始节点标记为已访问；

3.当队列不为空时，循环执行以下：

（1）出队一个节点；

（2）访问该节点；

（3）将该节点的所有的未访问的节点入队并更新标记为已访问；

（4）遍历完成

BFS算法的特点是按照层级进行遍历，先访问距离起始节点最近的节点，再次访问距离起始节点远一层的节点。依次类推，由于BFS需要使用队列来辅助实现，因此可以保证每个节点被访问且仅被访问一次。

BFS算法广泛应用于图的遍历，最短路径，连通性检测等问题，也可以解决一些搜索问题，例如在迷宫中找最短路径等。

伪代码如下：

int BFS(Node start, Node target) {
    入队(初始状态);
    visited[初始状态] = true;
    while(!空队) {
        for() { // 状态转换
            Node node = 队首元素;
            对node的处理，生成新node状态;
            if (visited[node] == true)
                continue;
            if (node == target) {
                输出答案;
                return 0;
            }
            v[node] = true;
            入队(node);
        }
    出队();
    }
}

3.对比与发现

DFS与BFS的区别：

BFS遍历节点是先进先出，DFS是先进后出；

BFS是一层一层访问，DFS是一条路一直访问到底，当前节点没有未访问的邻居节点时，然后回溯到上一个节点，不断的尝试，直到访问到目标节点或者是所有节点都已经访问。

BFS适用于求源点与目标节点距离最近的情况，例如：求最短路径。DFS更适合于求解一个任意符合方案中的一个或者遍历所有情况，例如：全排列、拓扑排序、求到达某一点的任意一条路径。

4.例题解析

本题选自洛谷B3625迷宫寻路

题目描述

机器猫被困在一个矩形迷宫里。

迷宫可以视为一个 \(n\times m\) 矩阵，每个位置要么是空地，要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。

机器猫初始时位于 \((1, 1)\) 的位置，问能否走到 \((n, m)\) 位置。

输入格式

第一行，两个正整数 \(n,m\)。

接下来 \(n\) 行，输入这个迷宫。每行输入一个长为 \(m\) 的字符串，# 表示墙，. 表示空地。

输出格式

仅一行，一个字符串。如果机器猫能走到 \((n, m)\)，则输出 Yes；否则输出 No。

样例 #1

样例输入 #1

3 5
.##.#
.#...
...#.

样例输出 #1

Yes

提示

样例解释

路线如下：\((1,1)\to (2,1) \to (3,1) \to (3,2)\to (3,3) \to (2, 3) \to (2, 4) \to (2, 5) \to (3, 5)\)

数据规模与约定

对于 \(100\%\) 的数据，保证 \(1 \leq n, m \leq 100\)，且 \((1,1)\) 和 \((n, m)\) 均为空地。

思路：`bfs`

我们可以逐层展开搜索：

搜索一步能到达的点；
搜索两步能到达的点；
搜索三步能到达的点；

这种方法我们成为广度优先搜索（宽度优先搜索，bfs）。

使用广度优先搜索就要使用到队列，存储待访问的点。

所以我们的 bfs 可以这么写：

把起始点 (1,1)(1,1) 入队；
如果队列非空：
弹出队首 (x,y)(x,y)；
判断 (x,y)(x,y) 是否非法，若非法，跳过；
把 (x,y)(x,y) 相邻的点入队；

AC码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=1000;
bool vis[N][N]; //定义一个二维数组用于标记是否访问过某个位置
int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; //定义一个二维数组表示四个方向的坐标偏移量
int main(){
    int r,c;
    cin >> r >> c; 
    vector<string>s(r); 
    for(int i=0;i<r;i++){
        cin >> s[i];
    }
    queue<pair<int,int>> q; //定义一个队列，用于进行广度优先搜索
    q.push({0,0}); //将起点入队
    vis[0][0]=true; //标记起点为已访问
    while(!q.empty()){
        pair<int,int> p=q.front(); //取出队首元素
        int x=p.first;
        int y=p.second;
        q.pop(); //将队首元素出队
        if(x==r-1&&y==c-1){
            cout << "Yes\n"; //如果到达终点，输出"Yes"并结束程序
            return 0;
        }
        for(int i=0;i<4;i++){ //遍历四个方向
            int xx=x+d[i][0]; //计算下一个位置的横坐标
            int yy=y+d[i][1]; //计算下一个位置的纵坐标
            if(xx<0||yy<0||xx>=r||yy>=c||vis[xx][yy]||s[xx][yy]!='.'){
                continue; //判断下一个位置是否合法，如果不合法则跳过该位置
            }else{
                q.push({xx,yy}); //将下一个位置入队
                vis[xx][yy]=true; //标记下一个位置为已访问
            }
        }
    }
    cout << "No\n"; //如果无法到达终点，输出"No"
    return 0;
}