一、广搜介绍

广度优先搜索是一种暴力算法，通过遍历一整张图来找寻结果。一般是使用队列来实现

1.原理

首先我们将根节点加入队列，然后遍历这个节点的全部方向，如果有满足条件的节点出现，就将其加入队列。

在全部方向遍历完之后，我们将遍历的节点出队列。然后接着重复上述的操作，直到队列为空，也就代表着图遍历完毕。

2.详解

上图为我们展示了BFS遍历的过程，接下来我们详细解释一下。

首先我们定义一个队列为q，这时队列是为空的。我们将root也就是根节点加入队列。

此时队列中的元素为：root。然后遍历与root相连的节点，发现有1和2,将其加入到队列中。遍历完之后将root出队列。

此时队列中的元素为：2,1。接下来遍历与1相连的节点，发现有3，4将其加入队列，然后1出队列。

此时队列中的元素为：4,3,2。然后遍历与2相连的节点，发现有5和6将其加入队列，然后再让2出队列。

以此类推，最后直到队列为空的时候就代表我们将图遍历了一次。

二、代码实现

举个例子，走迷宫，给一个n*m的二维数组表示迷宫，迷宫只由数字0和1组成，其中0代表可以走，而1代表墙。

现在我们要从左上角的（0,0）走到右下角的（n - 1,m - 1），其中我们每次可以在上，下，左，右四个方向中任走一步，

如果我们能到达右下角就输出能到达,不能就输出不能到达。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 首先我们要做一些初始化定义
int n, m;
int Map[50][50];
bool visit[50][50] = {false};
// 定义一个节点队列，里面包含两个参数x,也就是坐标
struct point
{
    int x, y;
}root;
queue<point> q;

//定义我们要走的方向上下左右四个方向。
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};


bool BFS(int x,int y){
    //初始化我们的起点
   root.x = x;
   root.y = y;
   //表示这个点是我们走过的
   visit[x][y] = true;
   q.push(root);
   while(!q.empty()){
       point node = q.front();//定义一个变量用于保存我们当前要遍历的节点
       q.pop();//将队首出队列
       //满足条件就直接返回
       if(node.x == n - 1 && node.y == m - 1)
           return true;
       for (int i = 0; i < 4;i++){
        //开始遍历我们要走的方向
           int next_x = node.x + dx[i];
           int next_y = node.y + dy[i];
        //判断一下，首先不能越界并且是可以走的，然后这个点是我们之前没有走过的，
        if(Map[next_x][next_y] == 0 && visit[next_x][next_y] == false && next_x >= 0 && next_y >=0 && next_x < n && next_y < m){
            //将这个节点设为已走过
            visit[next_x][next_y] = true;
            //更新节点值
            node.x = next_x;
            node.y = next_y;
            //将节点加入队列
            q.push(node);
        }
        
       }
   }
   return false;
}


int main(){
    cin >> n >> m;
    //建图
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> Map[i][j];
        }
    }
    if(BFS(0,0)){
        cout << "能走到";
    }
    else cout <<"不能走到";
    return 0;
}