广度优先搜索

学习
字数统计: 3k   |   阅读时长≈ 14 分钟

广度优先搜索

0. 概述

  • 广搜是基于队列实现的从根开始向下逐层扩展逐层访问的搜索遍历方法

1. 基于邻接表

image-20240510202644636

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
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=1e5+5;
vector<int> e[N]; // e[1]:结点1的相邻结点
int vis[N]; // vis[1]:结点1的访问状态,true:访问过了,false:未访问
queue<int> q; // 队列

void bfs() {
	vis[1]=1; // 假设结点1是根节点
	q.push(1);
	while(q.size()) {
		int x=q.front();
		q.pop();
		printf("%d 出队\n",x);
		// 扩展其儿子结点
		for(int y:e[x]) {
			if(vis[y]) continue; // 避免反复入队
			vis[y]=1;
			printf("%d 入队\n",y);
			q.push(y);
		}
	}
}

int n,m; // 每个结点扩展的边数

int main() {
	cin>>n>>m; // n个结点,.条边
	for(int i=1;i<=m;i++) {
		int a,b;
		cin>>a>>b; // 父在前
		// 无向图双向建边
		e[a].push_back(b);
		e[b].push_back(a);
	}
	bfs();
	return 0;
}

/*
8 7
1 2
1 3
2 4
2 5
2 6
3 7
3 8
*/

2. 基于链式前向星

  • 注意，因为链式前向星是头插，所以入队和出队顺序和基于邻接表（尾插）不太一样
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
73
74
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=1e5+5; // 最大结点数
const int M=(1e5+5)*2; // 最大边数(无向图)
int h[N]; // h[i]:结点i的起始边编号
int e[M]; // e[i]:第i条边到达的结点
int ne[M]; // ne[i]:第i条边的下一条边的编号
int idx; // 建边因子

int vis[N]; // 每个结点的访问状态

void add(int a,int b) {
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}

int n,m; // 每个结点扩展的边数

queue<int> q; // 维护序列的队列

void bfs() {
	vis[1]=true;
	q.push(1);
	while(q.size()) {
		int x=q.front();
		q.pop();
		printf("%d 出队\n",x);
		// 遍历连接x的所有边
		for(int i=h[x];i!=-1;i=ne[i]) {
			int j=e[i]; // 取出第i条边所达结点
			if(vis[j]) continue;
			vis[j]=true;
			printf("%d 入队\n",j);
			q.push(j);
		}
	}
}

int main() {
	memset(h,-1,sizeof h); // 初始化
	cin>>n>>m; // n个结点,.条边
	for(int i=1;i<=m;i++) {
		int a,b;
		cin>>a>>b; // 父在前
		// 无向图双向建边
		add(a,b);
		add(b,a);
	}
	bfs();
	return 0;
}

// 注意,因为是头插,所以入队和出队顺序和基于邻接表不太一样

/*
8 7
1 2
1 3
2 4
2 5
2 6
3 7
3 8
 */

3. 基于二维数组（地图）

3.1. 单源BFS

3.1.1. 象棋马的遍历

题目描述：在象棋棋盘中，马从 $(0,0)$ 跳到 $(fx,fy)$【自行输入】，已知马只能向右跳，求到达终点所需最少步长并输出其路径

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
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=1e3+5;
// 只能向右走,说明在列方向上的变化只能是正值
const int dx[]={0,1,2,-1,-2};
const int dy[]={0,2,1,2,1};
int dist[N][N]; // 初始化为-1,也把dist当作st数组用
int ans; // 存储最短路径
int fx,fy; // 终点是(fx,fy),行是m,列是n
queue<PII> q; // 放的是坐标

PII pre[N][N]; // 记录路径

// 只调用一次
int bfs(int x,int y) {
	dist[x][y]=0;
	q.push(make_pair(x,y));
	while(q.size()) {
		// 取出队头
		PII t=q.front();
		q.pop();
		// 遍历四个方向
		// 一定不会往回走
		for(int i=1;i<=4;i++) {
			int xx=t.x+dx[i];
			int yy=t.y+dy[i];
			// 越界处理
			if(xx<0 || yy<0 || xx>fx || yy>fy) continue;
			q.push(make_pair(xx,yy));
			dist[xx][yy]=dist[t.x][t.y]+1;
			pre[xx][yy]=make_pair(t.x,t.y); // [xx,yy]的前驱是[t.x,t.y]
			// 找到终点了
			if(xx==fx && yy==fy) {
				return dist[xx][yy];
			}
		}
	}
	return -1; // 找不到
}

int main() {
	cin>>fx>>fy;
	int sx=0,sy=0; // 起点
	cout<<bfs(sx,sy);
	int x=fx,y=fy; // 回溯路径
	cout<<endl;
	vector<PII> v; // 记录正向路径
	while(x!=sx || y!=sy) { 
		v.push_back(make_pair(x,y));
		PII prev=pre[x][y];
		x=prev.x;
		y=prev.y;
	}
	v.push_back(make_pair(sx, sy)); // 添加起点到路径中 
	for(int i=v.size()-1;i>=0;i--) { // 输出路径要倒序输出
		if(i!=0) cout<<"("<<v[i].x<<","<<v[i].y<<")"<<"-->";
		else cout<<"("<<v[i].x<<","<<v[i].y<<")";
	}
	return 0;
}

3.1.2. 迷宫最短路

推荐学习视频：B12 BFS 迷宫 最短路_bilibili
题目描述：$n$ 行 $n$ 列的二维地图中，$1$ 表示墙壁，$0$ 表示可走的路，只能朝上下左右四个方向走，求最短路径长度并输出这条路径

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=1e3+5;
// 偏移量
const int dx[]={0,1,-1,0,0};
const int dy[]={0,0,0,1,-1};

int n;
int g[N][N]; // 地图,01存储,兼状态数组
int dist[N][N]; // dist[i][j]:(i,j)到起点(1,1)的距离
queue<PII> q; // 维护序列的队列
PII pre[N][N]; // pre[i][j]:(i,j)的上一步的坐标(记录最短路)
int fx,fy; // 终点

int bfs(int x,int y) {
	dist[x][y]=0;
	q.push({x,y}); // 左上角初始加入队列
	g[x][y]=1; // 渲染成墙壁,表示走过了
	while(q.size()) {
		PII t=q.front(); // 取出队头
		q.pop();
		// 遍历四个方向
		for(int i=1;i<=4;i++) {
			int xx=t.x+dx[i];
			int yy=t.y+dy[i];
			// 约束条件
			// 1) 越界处理
			if(xx<1 || xx>n || yy<1 || yy>n) continue;
			// 2) 必须为可走&&必须没走过
			if(g[xx][yy]==1) continue;
			// 占据方案
			g[xx][yy]=1;
			dist[xx][yy]=dist[t.x][t.y]+1; // 步长+1
			pre[xx][yy]={t.x,t.y}; // 记录上一步
			cout<<t.x<<','<<t.y<<"-->"<<xx<<','<<yy<<endl;
			if(xx==fx && yy==fy) return dist[xx][yy];
			q.push({xx,yy});
			// 如果找到终点
		}
	}
	return -1; // 找不到最短路
}

int main() {
	cin>>n;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			cin>>g[i][j];
		}
	}
	fx=n,fy=n;
	cout<<bfs(1,1)<<endl; // 从(1,1)广搜
	cout<<dist[n][n]<<endl;
	vector<PII> path; // 存储路径
	// 一直回溯到起点
	while(fx!=1 || fy!=1) {
		printf("(%d,%d)的上一个位置是(%d,%d)\n",fx,fy,pre[fx][fy].first,pre[fx][fy].second);
		path.push_back({fx,fy});
		PII prev=pre[fx][fy];
		fx=prev.x;
		fy=prev.y;
	}
	path.push_back({1,1});
	reverse(path.begin(),path.end());
	for(int i=0;i<path.size();i++) {
		if(i!=path.size()-1) printf("(%d,%d)->",path[i].first,path[i].second);
		else printf("(%d,%d)",path[i].first,path[i].second);
	}
	return 0;
}
/*
5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0 
0 1 1 1 0
0 0 0 1 0
*/

3.1.3. 抓住那头牛

推荐学习视频：B15 BFS 抓住那头牛_bilibili
题目描述：人和牛在同一直线上，初始位置分别为 $x$ 和 $y$，牛不动，人每次可以前进 $1$ 步、后退 $1$ 步或者直接走到 $2×x$ 的位置，计算追上牛的最小步数

  • 对于起点先加入队列，随后每次取出队头分别处理前进一步、后退一步以及 $×2$ 后的步数，因为是逐层扩展，所以第一次遍历到的时候所用到的步数一定是最小的
  • 同时我们约束其上下界，下界为 $0$ ，因为题目要求 $x,y>=0$ ，上界为题目给的数据范围 $1e5$，因为 $x×2,\ x-1,\ x-1$ 不如 $x-1,x×2$ 更优，所以可以约束其上界
  • 本题还需要学习的一点在于用 $dist$ 数组进行剪枝，限制第一次来到这一步才对值进行更新，根据 $BFS$ 逐层扩展的原理，这样求出来的本身也是最小值
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
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=1e5+5;
int x,y,dist[N]; // dist[i]:走到i所需要的最少步数

queue<int> q;

void bfs() {
	memset(dist,-1,sizeof dist);
	dist[x]=0; // 起点
	q.push(x); 
	while(q.size()) {
		int x=q.front();
		q.pop();
		// 下面三种情况的约束条件:都是没走过(因为逐层扩展,所以第一次遇到一定最小)并且不越界
		// 下面的三个if是并列关系,相当于一个结点会扩展3次,前进一步/后退一步和×2
		// 其实dist数组的作用相当于剪枝了,因为每个结点只能被扩展一次
		// 易证明,x*2再-1-1,不如x-1,x*2更优,故有上界x<=10^5
		if(x+1<N && dist[x+1]==-1) {
			dist[x+1]=dist[x]+1; // 前进一步
			q.push(x+1);
		}
		// 坐标范围本身(x,y)都>0
		if(x-1>0 && dist[x-1]==-1) {
			dist[x-1]=dist[x]+1; // 后退一步
			q.push(x-1);
		}
		if(2*x<N && dist[2*x]==-1) {
			dist[2*x]=dist[x]+1; // 走到2*x的位置
			q.push(2*x);
		}
		// 如果走到终点
		if(x==y) {
			cout<<dist[y]<<endl; 
			return;
		}
	}
}

int main() {
	int T;
	cin>>T;
	while(T--) {
		cin>>x>>y;
		bfs();
	}
	return 0;
}
/*
输入样例:
1
5 17
输出样例:
4
 */

3.2. 多源BFS

3.2.1. 距离矩阵

推荐学习视频：B13 多源BFS 矩阵距离_bilibili
题目描述：即是说求图中每一个 $0$ 距离自己最近的 $1$ 的曼哈顿距离，从而构成一个新的矩阵 $B$

image-20240512154726043

  • 为了求每个 $0$ 距离自己最近的 $1$ 的曼哈顿距离，如果计算遍历到每个 $0$ 时分别去寻找距离自己最近的 $1$ 并打擂取得最小值，时间复杂度很会高
  • 所以可以从每个 $1$ 做洪水覆盖，即多源 $BFS$，先来到这个点的距离一定是最短的，因为 $BFS$ 是逐层扩展
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
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=1e3+5;
const int dx[]={0,1,-1,0,0};
const int dy[]={0,0,0,1,-1};
char g[N][N]; // 地图
int dist[N][N]; // 存储到源点的距离,兼职判重
int n,m; // n行m列

queue<PII> q; // 多源,把每个1都放入队列

void bfs() {
	memset(dist,-1, sizeof dist); // 均初始化为不可达
	// 遍历地图
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			// 多源BFS,区别就是把多个源点都加入队列
			if(g[i][j]=='1') {
				dist[i][j]=0; // 到自己的距离为0
				q.push({i,j});
			}
		}
	}
	while(q.size()) {
		auto t=q.front();
		q.pop();
		for(int i=1;i<=4;i++) {
			int xx=t.x+dx[i];
			int yy=t.y+dy[i];
			// 1) 越界处理
			if(xx<1 || xx>n || yy<1 || yy>m) continue;
			// 2) 走过则跳过
			if(dist[xx][yy]!=-1) continue;
			dist[xx][yy]=dist[t.x][t.y]+1; // 洪泛计算距离
			q.push({xx,yy});	
		}
	}
}

int main() {
	cin>>n>>m;
	// 输入地图
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			cin>>g[i][j];
		}	
	}
	bfs();
	for(int i=1;i<=n;i++,puts("")) {
		for(int j=1;j<=m;j++) {
			cout<<dist[i][j]<<' ';
		}	
	}
	return 0;
}
/*
3 4
0 0 0 1
0 0 1 1
0 1 1 0
*/
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2015-2024 John Doe
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信