bfs学习记录：模板/思路汇总

发表于 分类于 阅读次数： 本文字数： 1.8k 阅读时长 ≈ 7 分钟

HB小咸鱼学习记录

一点看法

蓝桥杯刷了不少的搜索题，但是bfs的题很少，大部分都是dfs的题。
但是去年蓝桥杯就考了bfs，所以还是得好好刷题。
bfs由于是一个循环进行搜索，所以没法回溯，因而每个点位只能被走一次。这样加快了搜索速度，但是由于每个点只能走一次导致无法列举出所有的可走路径。而这样的好处是避免了绕远路，搜索到结果时一定是最短路。所以大部分的求最短路的题都用bfs.

自我对于“广度优先搜索”的理解

bfs,字面来看就是以广度为优先的搜索方式。搜索时以原点向四周扩散。如果说dfs是“搜完一个屋子再搜另一个屋子”，那bfs就是“把每个屋子的柜子搜了再搜每个屋子的桌子……”这样层层深入的搜索。这样可以优先搜索物品可能在的地方，从而减少搜索的时间。
就像我们规定以“前左右”的顺序走迷宫，而在寻找迷宫的出口时就可以看成进行了一次搜索。我们首先记录下来第一个路口能前往哪几个路口，随后再按照规定的顺序（前左右）查看这几个路口的又能前往哪几个路口。途中前往过的路口要进行标记，防止重复的查看。直到查看一个路口，它可以前往到终点或者它就是终点，此时搜索结束。我们查看的轮数就是前往该终点的最小步数。而在搜索过程中，我们可以使用适当的数据结构来储存前往终点所经过的路口，这就是最短路径。
这样进行搜索的范围大，查找到终点的路径始终是最短路径。但缺点是我们没办法迭代出所有的可前往终点的路径。

bfs的大致思路

首先，如上个片段所说，我们首先需要一个二维数组，来对迷宫进行标记，标记出可以走的点和障碍（不可以走的点）。
其次，我们建立一个队列，把起点加入到队列中。
接着，我们建立一个while循环，设定在队列不为空的时候执行循环。
循环中，我们首先获取队列的头结点坐标，随后我们需要对移动的规则进行规定。例如上文的例子规定的“上左右”，我们可以用一个二维数组来储存移动后坐标的变化：

1
int direction[4][2] = {{0,-1},{-1,0},{1,0},{0,1}};

这个数组里面的四组数据就分别代表“上左右下”，在对坐标变换时进行

1
2
int x1=x+direction[a][0];
int y1=y+direction[a][1];

即可实现对坐标的变化。我们按照这个顺序，对头结点的周围进行判断，如果可以前往的话，就将变换后的数据点加入队列。然后将新点（x1,y1）的状态进行更改，代表你已经来过这里了。防止重复的搜索。
最后，我们需要设定上一步循环的中止条件，从而在找到出口时停止或者返回一些信息。我们常常在循环中获取头结点后进行判定，如果头结点数据是我们想要搜索到的信息，我们就中止循环。

bfs的大致模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void BFS(传入的数据)
{
	queue<int>q; //建立一个队列
	q.push(初始坐标); //把头结点（初始点）加入队列
	while(队列不为空) 
	{
		top = q.front(); //取出队首元素top
		if(队首元素top就是你要搜索的目标) 
		{
			执行一些操作
			return;
		}
		top.pop(); //将队首元素出队；
		for(按顺序寻找top的所有子节点)
		{
			把可以前往的子节点入队
			标记入队的子节点，防止下次重复入队
		}
	}
}

bfs例题

蓝桥杯 学霸的迷宫

题干
样例输入
Input Sample 1:
3 3
001
100
110
样例输出
Output Sample 1:
4
RDRD

题目链接

这一题算是bfs的经典例题，题目不止让求了最短的步数，还让输出了最短的路径。
所以我们在队列结点的数据结构中添加了一个string字符串，用来储存到达某个点的最短路径。
在找到终点时，输出最短步数和最短路径即可。
ac代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h> 
using namespace std;

struct data	//队列里的数据结构 
{
	int x;	//坐标x 
	int y;	//坐标y 
	int times;	//步数 
	string road;	//走过的路径
	data(int a,int b,int d,string c)	//构造函数 
	{
		x=a;
		y=b;
		times=d;
		road = c;	
	}	
};
queue<data>datas;	//队列用来存放点位数据 
bool maps[501][501];	//存放迷宫地图的点位 false代表可前往 true代表不可前往 
char fx[] = {'D','L','R','U'};	//方向ascii码从小到大排列 
int site[4][2] = {{0,1},{-1,0},{1,0},{0,-1}};	//下 左 右 上的坐标变化 

void bfs(int n,int m)	//传参为迷宫的大小 n为宽 m为长 
{
	datas.push(data(1,1,0,""));	//把起始点压入队列 
	maps[1][1]=true;	//标记初始点已走过 
	while(!datas.empty())	//如果队列不为空 
	{
		data now = datas.front();	//声明一个结构体变量 让now变量指向队列的头结点
		datas.pop();	//弹出头结点 
		//cout<<now.x<<" "<<now.y<<endl; 
		if(now.x==n&&now.y==m)	//如果头结点就是要找的点 就搜索结束 
		{
			cout<<now.times<<endl<<now.road<<endl;	//输出走过的路径 和步数 
			return; 
		} 
		for(int temp=0;temp<4;temp++)	//开始查找该点的四周点位 （因为只有上下左右4个走法 所以循4次 
		{
			int x1=now.x+site[temp][0];	//变换过的x坐标 
			int y1=now.y+site[temp][1]; //变换过的y坐标 
			if(maps[y1][x1])	//如果该点已经走过或者有障碍 跳过 
				continue;
			if(x1<1||y1<1||x1>n||y1>m) 	//如果坐标超出范围 就跳过此循环
				continue;
			datas.push(data(x1,y1,now.times+1,now.road+fx[temp]));	//把新点位压入队列 路径加上新选择的fx[temp] 
			maps[y1][x1] = true;	//标记已走过 
		}
	} 
}

int main()
{
	memset(maps,false,sizeof(maps));		//初始化 
	int x,y;	//接收迷宫大小
	char input;	
	cin>>y>>x;
	getchar();
	for(int y1=1;y1<=y;y1++) 	//迷宫长 
	{
		for(int x1=1;x1<=x;x1++)	//迷宫宽 
		{
			cin>>input;
			if(input=='1')
				maps[y1][x1]=true;	//如果输入是1就标记不可走
		}
		getchar();
	}
 	
 	bfs(x,y);	//bfs 迷宫长宽 与 xy坐标是相反的 所以传反着的坐标 
	
	return 0;
}

小结

在使用bfs中，要根据题目数据选择合适的数据类型。
bfs的题中往往不会只让你输出最短路径的长度，一般还会带点别的东西，所以要建立合适的结构来储存数据。
bfs的常用环境
一般是用来寻找不带权值的图的最短路。问题关键词常为“能否到达”、“最短路径”。
目前来看蓝桥杯中对bfs的考察度往往低于dfs，但是蓝桥杯最近几年对bfs的考察也在变多，所以还得好好练。
总之，还是得多刷题，多积累经验。