BFS与队列以及DFS与BFS的区别

发布时间:2024年01月18日

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好比一群人走不同的方向找到结果,如果路被走过或者到达某种限制条件就会停下。

好了,本期内容到这里了,感谢收看,记得三连支持哈,后期会继续带来算法基础分析。

文章来源:https://blog.csdn.net/2302_79840586/article/details/135672545
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。