DFS与BFS是基本的两种暴力搜索技术，用于解决树,图的遍历问题，在前面的博客写到了一些基础的DFS解决的问题，本期给大家带来BFS的分析过程。
对于我个人的理解，DFS和BFS无非是两大模板型，DFS是利用递归（or栈）的方法进行深度搜素，而BFS是利用队列的思想，拿我前面的文章内讲述了DFS走迷宫问题，枚举所有方向通过递归找到最终的答案，那么如果利用BFS的思想该如何分析呢？
举个例子：
.? ? .? ? .? ? .? ? .? ? .? ?
.? ? #? ?.? ? .? ? .? ? #
.? ? .? ? .? ? .? ? #? ?.
#? ?.? ? .? ? .? ? .? ? .
.? ? .? ? .? ? #? ?.? ? .?
如图是一个长方形的房间，'.'为可以走的瓷砖,'#'为陷阱，请你输出从初始的瓷砖开始出发可以到达的瓷砖总数量（不能重复经过同一个瓷砖）。
我们假设从左上角出发，那么先将该点（1）放入队列，那么可走的方向为向下（2）或者向右（3），然后将（1）出队并将（2）和（3）入队，这时队列内：2 3，然后判断（2）点的情况为向下（4）或者向右（5），那么将（2）出队并将（4）和（5）入队，重复此过程......，直到最后队列剩余：....n - 3,n - 2,n - 1,n（这几个点没有方向可走），这时将这几个点全部出队，此时队列为空即为结束，分析过程结束，接下来开始写代码....
最开始的坐标按照DFS走迷宫那篇文章的写法：
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1);在DFS中通过递归的方式将坐标作为函数的形参来更改，那么在BFS中需要将队列每个元素通过结构体改为含有坐标形式的结构体元素：
struct node
{
int x;//横坐标
int y;//纵坐标
};
随后建立队列：queue<node>q
这里给大家讲述一下队列的基础知识：
队列与栈不同，栈是先进后出，而队列为先进先出，所以这里满足BFS广搜的特点
#include <queue>
queue <数据类型> q;
q.push(n);? ? ? ? ? ? ? ?//将n入队
q.front();? ? ? ? ? ? ? ? ?//返回队首元素（不会删除）
q.pop();? ? ? ? ? ? ? ? ? //删除队首元素
q.back();? ? ? ? ? ? ? ? //返回队尾元素
q.size();? ? ? ? ? ? ? ? ?//返回元素个数
q.empty();? ? ? ? ? ? ? //检查队列是否为空
?随后根据上面的解释，通过反复的入栈出栈写出的代码：
const int N = 1000;
char room[N][N];
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int xmax,ymax;//边界
#define Check(x,y) (x < xmax && x >= 0 && y < ymax && y >= 0) //判断是否能出房间
typedef struct node
{
int x;
int y;
};
int num = 0;//计数
void BFS(int x,int y)
{
queue <node> q;//队列q
node start , next;
start.x = x;
start.y = y;
q.push(start);//将该点入队
while(!q.empty())//判断队列q是否为空
{
start = q.front();//队首元素的刷新
q.pop();//队首元素出栈
for(int i = 0;i < 4;i++)//跟DFS类似，枚举四种方向
{
next.x = start.x + dx[i];
next.y = start.y + dy[i];
if(Check(next.x,next.y) && room[next.x][next.y] == '.')//判断是否在棋盘内以及下一个点是否可以使用
{
num++;//计数
room[next.x][next.y] = '#';//该点被走过，被记录（也可以用bool数组判断）
q.push(next);//将该点入队
}
}
}
}上面代码为BFS入队出队的代码剩下的主函数代码相信聪明的你肯定会写了，这里就不展示了。
这里的代码其实与DFS的递归搜索颇为相似：
int num = 0;
void DFS(int x,int y)
{
for(int i = 0;i < 4;i++)
{
int next_x = x + dx[i];
int next_y = y + dy[i];
if(Check(next_x,next_y) && room[next_x][next_y] == '.')
{
num++;
room[next_x][next_y] = '#';
DFS(next_x,next_y);
}
}
}我们在分析DFS的过程其实类似栈的出入，也就是DFS算法也可以用栈的形式写。
DFS好比一个人走所有路直到走遍所有的路且不重复走，BFS好比一群人走不同的方向找到结果，如果路被走过或者到达某种限制条件就会停下。
好了，本期内容到这里了，感谢收看，记得三连支持哈，后期会继续带来算法基础分析。