c++宽度优先搜索BFS

宽度优先搜索，又叫做广度优先搜索，简称宽搜（BFS），是另一种常见搜索算法（还有一种是深搜）。宽搜是一种图的搜索算法，运用非常广泛，也很基础，是每一个编程者必学的算法。因为它是一个很便捷的算法，可拓展性也很高。一些图的最短路算法基本上都是用的是宽搜，或者是基于宽搜。比如Dijstra(求单源最短路径的)，和Prim(最小生成树)。这两个都是比较进阶一点的算法，只有把宽搜学扎实了，才有拓展的可能。总

zhaoniuniu0309

2077人浏览 · 2023-07-27 18:40:03

zhaoniuniu0309 · 2023-07-27 18:40:03 发布

今天我们学习c++基础算法：宽度优先搜索。由于它的重要性，所以有必要详细讲解一下。

介绍

宽度优先搜索，又叫做广度优先搜索，简称宽搜（BFS），是另一种常见搜索算法（还有一种是深搜）。

宽搜是一种图的搜索算法，运用非常广泛，也很基础，是每一个编程者必学的算法。因为它是一个很便捷的算法，可拓展性也很高。一些图的最短路算法基本上都是用的是宽搜，或者是基于宽搜。比如Dijstra(求单源最短路径的)，和Prim(最小生成树)。这两个都是比较进阶一点的算法，只有把宽搜学扎实了，才有拓展的可能。

总之，宽搜必学！

实现过程

宽搜的具体方法就是以一个节点为起点，将它的所有子节点列入待处理。然后从待处理中的节点中一个一个处理。先判断这个节点是否为终点，如果不是，就将它的所有子节点都列入待处理。判断玩这个点的所有子节点后，再从待处理的节点选一个，进行处理，直到到达了终点。

为什么叫做宽搜呢？因为它是把当前节点的所有子节点一起处理，然后按顺序处理子节点的所有子节点，也就是说如果是一棵树的话，款搜的顺序应该是一层一层的，这也就保证了搜到答案的路径一定是最短的，所以宽搜被广泛运用于最短路算法中。不过宽搜是一种盲目搜索，也就是说他会在搜到答案之前一直搜索下去，直到找到答案或者搜遍了整个图。所以宽搜也是有很多优化的。

下面配了几张图来辅助理解宽搜的实现过程。

首先，我们有一棵树：

其中，节点6为目标节点。

我们先从根节点开始，一步一步搜索。

发现1号节点不是目标节点，将它的子节点进行处理。

发现2节点和3节点都不是目标节点，我们先处理2节点的所有子节点。

发现2节点的所有子节点都不是目标节点，再处理2的下一个点的子节点，也就是3的子节点。

我们找到了目标节点，搜索也就结束了。

模板

知道了具体的实现过程，我们还要知道怎样将思路转化为代码。下面就给出宽搜的模板：

queue<struct_type>q;//用队列存储需要处理的点的信息，一般队列类型都是存点的信息的结构体的类型 
q.push(根节点的信息);
while(队列不为空){//也就是还有没有处理的点 
	int now = q.front();
	q.pop();
	if(now 是终点){
		输出答案
		break; 
	}
	for(int i = ?; i <= ?; i++){
		枚举这个点的所有子节点
		if(子节点合法){
			子节点标记为访问;
			q.push(子节点);
		} 
	}
}

可以看到，宽搜存储待处理的点的的信息用的是队列，所以也要熟练掌握队列相关知识。

例题详解

光说不练当然不会掌握，下面我们就来结合例题来详细讲解宽搜。

1.迷宫寻路

题目描述

机器猫被困在一个矩形迷宫里。

迷宫可以视为一个 n×m 矩阵，每个位置要么是空地，要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。

机器猫初始时位于(1,1) 的位置，问能否走到 (n,m) 位置。

输入格式

第一行，两个正整数 n,m。

接下来 n 行，输入这个迷宫。每行输入一个长为 m 的字符串，# 表示墙，. 表示空地。

输出格式

仅一行，一个字符串。如果机器猫能走到 (n,m)，则输出 Yes；否则输出 No。

输入输出样例

输入 #1

3 5
.##.#
.#...
...#.
输出 #1

Yes
说明/提示

样例解释

路线如下：(1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3)→(2,4)→(2,5)→(3,5)。

数据规模与约定

对于 100% 的数据，保证 1≤n,m≤100，且 (1,1) 和 (n,m) 均为空地。

首先，这一题是一道很经典的搜索题。搜索题？没错，这一题深搜和宽搜都可以做。本文我们讲款搜的做法，深搜的做法也请大家好好思考一下。

我们就通过这一道很入门的题目来走进宽搜。

首先，我们要存储每个节点的信息，分别是横坐标和纵坐标。我们就用一个结构体来存储。

struct node{
	int x, y;
};

有人就说了，不可以用一个二维数组来存储点吗？为什么要用结构体呢？这样方便我们用数组啊！

我们都知道，数组的定义是这样的：

queue<数据类型>q

其中，数据类型可以任意的，包括自定义的结构体！所以我们就可以这样存储每个点的信息了。

struct node{
	int x, y;
};
queue<node>q

然后进入重点内容，也就是宽搜的主体。

我们从起点，也就是(1,1)这个点开始搜，首先把这个点入队。

q.oush({1, 1});

但是，宽搜和深搜一样，也需要有访问标记，所以我们把(1, 1)这个点标记为访问过。

然后我们进入宽搜函数。首先，我们要获得队头的信息，并存储在 now 这个变量中，然后将队头出队。

node now = q.front();

然后对 now 进行判断。如果 now 就是终点，那么直接输出 “Yes” 并 break。否则，就枚举 now 的每个子节点，如果子节点合法，就将它入队。我们怎样快速枚举一个点的子节点呢？这和深搜中的类似。如果我们规定向上纵坐标减一，向下加一，向左横坐标减一，向右加一。那我们就可以用一个数组来表示横、纵坐标的加减情况。

int dx[] = {0, 0, -1, 1},
	dy[] = {-1, 1, 0, 0};

这样就可以用一个循环来枚举子节点了。而判断合法，我们只需要判断当前点是否在地图中，并且没有用过，也就是访问标记为零，最后就是这个点必须是条路。最后一条看似是最容易想到的，但也是最容易忘记的。

这样我们就得到了 check() 函数。

bool check(int x,int y){
    return (a[x][y] && !vis[x][y]);
}

因为我把地图中的字符换成了数字，如果是路就换成1，所以判断的时候只需要判断 a 数组是否为1，以及这个位置没有访问过。

得到了一个合法的点，我们就把它入队。然后不断重复上面的操作，这样就得出了完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int n, m;
bool a[N][N], vis[N][N];
int dx[] = {0, 0, -1, 1},
	dy[] = {-1, 1, 0, 0};
struct node{
	int x, y;
};
queue<node>q;
bool check(int x,int y){
    return (a[x][y] && !vis[x][y]);
}
void bfs(int x,int y){
    while(!q.empty()){
        node now = q.front();
        q.pop();
        int x1 = now.x, y1 = now.y;
        if(x1 == n && y1 == m){
            printf("Yes\n");
            return;
        }
        for(int i = 0; i < 4; i++){
            int xx = x1 + dx[i];
            int yy = y1 + dy[i];
            if(check(xx, yy)){
                vis[xx][yy] = 1;
                q.push({xx, yy});
            }
        }
    }
    printf("No\n");
}
int main(){
    char c;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> c;
            if(c == '.') a[i][j] = 1;
        }
    }
    q.push({1, 1});
    vis[1][1] = 1;
    bfs(1, 1);
    return 0;
}

另外，这题如果用深搜的话，还需要一点点的优化，而宽搜只需要一个模板，这也侧面印证了宽搜可以找到最短路，所以在解决最短路是宽搜要比深搜有天然优势。

2.马的遍历

题目描述

有一个 n×m 的棋盘，在某个点 (x,y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数，分别为 n,m,x,y。

输出格式

一个 n×m 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 −1）。

输入输出样例

输入 #1

3 3 1 1

输出 #1

0    3    2    
3    -1   1    
2    1    4

说明/提示

数据规模与约定

对于全部的测试点，保证 1≤x≤n≤400，1≤y≤m≤400。

这也是一道比较经典的基础 BFS，有很多的变种，不过万变不离其宗，我们先学习最基础的。

先说大体思路：我们前面已经讲过，宽搜搜索到一个点时，路径必定是最短的。所以我们只要搜索一次，将整个图都遍历一遍，每次搜索下一个点都把 step ++，这样就知道访问到这个点时已经走了多少步。所以我们存储点的结构体要加一个变量： step，也就是走到当前这个点最少花费了多少步。并且，这一题没有所谓的终点，目标就是把整个图遍历一遍，所以我们没有边界条件，只需要 while(!q.empty()) 就行了。

再说几个要注意的点：

1.以前我们枚举下一个点时按的是上、下、左、右的顺序枚举，而本题是按照马的走法，所以我们要重新定义偏移数组：

int dx[8]={1, 2, 2, 1, -1, -2, -2, -1},
	dy[8]={-2, -1, 1, 2, -2, -1, 1, 2};

这样就可以模拟马的走法了。

2.每次获取队头时别忘记出队，q.pop()。

3.每次入队一个新的点时将 step ++。

4.输出要按照指定格式！题目里面没有说，但是样例很明显，要按指定的场宽输出！可以这样实现：

for(int i = 1; i <= n; i++){
	for(int j = 1; j <= m; j++){
		cout << setw(5) << a[i][j];
	}
	cout << endl;
}

好了，重点都讲完了，大家先自己打代码，再看我的代码进行优化。

#include<bits/stdc++.h>
using namespace std;
int n, m, sx, sy, a[405][405];
int dx[8]={1, 2, 2, 1, -1, -2, -2, -1},
	dy[8]={-2, -1, 1, 2, -2, -1, 1, 2};
struct node{
	int x, y, step;
};
queue<node>q;
void bfs(){
	while(!q.empty()){
		node now = q.front();
		q.pop();
		for(int i = 0; i < 8; i++){
			int xx = now.x + dx[i];
			int yy = now.y + dy[i];
			if(xx <= n && xx >= 1 && yy <= m && yy >= 1 && a[xx][yy] == -1){
				a[xx][yy] = now.step + 1;
				q.push((node){xx, yy, now.step + 1});
			}
		}
	}
}
int main(){
	cin >> n >> m >> sx >> sy;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			a[i][j] = -1;
		}
	}
	a[sx][sy] = 0;
	q.push((node){sx, sy, 0});
	bfs();
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cout << setw(5) << a[i][j];
		}
		cout << endl;
	}
	return 0;
}

这一题很基础，要完全消化。

3.奇怪的电梯

题目描述

呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 i 层楼（1≤i≤N）上有一个数字 Ki（0≤Ki≤N）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如 3，3，1，2，5 代表了 Ki（K1=3，K2=3，……），从 1 楼开始。在 1 楼，按“上”可以到 4 楼，按“下”是不起作用的，因为没有 −2 楼。那么，从 A 楼到 B 楼至少要按几次按钮呢？

输入格式

共二行。

第一行为三个用空格隔开的正整数，表示 N,A,B（1≤N≤200，1≤A,B≤N）。

第二行为 N 个用空格隔开的非负整数，表示 Ki。

输出格式

一行，即最少按键次数，若无法到达，则输出 -1。

输入输出样例

输入 #1

5 1 5
3 3 1 2 5

输出 #1

说明/提示

对于 100% 的数据，1≤N≤200，1≤A,B≤N，0≤Ki≤N。

这一题看似有点复杂，其实直接用模板进行修改就能 AC。我们先来想一想怎样存储点的信息。第一个就是该点的编号，其次一个就是到达这个点的最少步数，这个是在搜索过程中计算的。然后就是怎样枚举子节点，其实这题中的子节点就是当前楼层可以到达的楼层。只要用当前点的编号（也就是楼层）加上和减去这一层楼上表的数字，并判断是否在1楼到 n 楼之间，如果是就入队。

有了思路，实现就不难了。要注意的还是那几个点：起始节点要标记为访问，记得要出队，找到了就将答案存储到 ans 种并 break 。以下是代码，不过看代码之前必须要先尝试一遍：

#include<bits/stdc++.h>
using namespace std;
int n, a, b, num[205], ans;
bool vis[205], flag;
struct node{
	int id, step;
};
queue<node>q;
void bfs(){
	while(!q.empty()){
		node now = q.front();
		q.pop();
		if(now.id == b){
			flag = 1;
			ans = now.step;
			break;
		}
		if(now.id + num[now.id] <= n && !vis[now.id + num[now.id]]){
			q.push({now.id + num[now.id], now.step + 1});
			vis[now.id + num[now.id]] = 1;
		}
		if(now.id - num[now.id] >= 1&& !vis[now.id - num[now.id]]){
			q.push({now.id - num[now.id], now.step + 1});
			vis[now.id - num[now.id]] = 1;
		}
	}
} 
int main(){
	cin >> n >> a >> b; 
	for(int i = 1; i <= n; i++) cin >> num[i];
	q.push({a, 0});
	vis[a] = 1;
	bfs();
	if(flag) cout << ans << endl;
	else cout << -1 << endl;
	return 0;
}

优化

关于宽搜的优化并不常见，因为需要优化宽搜的时候一般情况下都有别的算法可以代替。不过BFS的优化也有。比如用哈希表存状态，进行状压。用优先队列，将待处理的点排序等等。不过都比较复杂，一篇文章写不下，而且具体情况需要结合具体题目，本文主要是一个入门。如果大家都有需求的话我后面专门讲搜索的优化（包含深搜）。