当前位置:   article > 正文

c++宽度优先搜索BFS_bfs c++

bfs c++

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

介绍

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

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

总之,宽搜必学!

实现过程

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

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

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

首先,我们有一棵树:

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

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

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

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

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

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

模板

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

  1. queue<struct_type>q;//用队列存储需要处理的点的信息,一般队列类型都是存点的信息的结构体的类型
  2. q.push(根节点的信息);
  3. while(队列不为空){//也就是还有没有处理的点
  4. int now = q.front();
  5. q.pop();
  6. if(now 是终点){
  7. 输出答案
  8. break;
  9. }
  10. for(int i = ?; i <= ?; i++){
  11. 枚举这个点的所有子节点
  12. if(子节点合法){
  13. 子节点标记为访问;
  14. q.push(子节点);
  15. }
  16. }
  17. }

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

例题详解

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

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) 均为空地。

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

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

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

  1. struct node{
  2. int x, y;
  3. };

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

我们都知道,数组的定义是这样的:

queue<数据类型>q

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

  1. struct node{
  2. int x, y;
  3. };
  4. queue<node>q

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

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

q.oush({1, 1});

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

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

node now = q.front();

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

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

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

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

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

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

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

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 105;
  4. int n, m;
  5. bool a[N][N], vis[N][N];
  6. int dx[] = {0, 0, -1, 1},
  7. dy[] = {-1, 1, 0, 0};
  8. struct node{
  9. int x, y;
  10. };
  11. queue<node>q;
  12. bool check(int x,int y){
  13. return (a[x][y] && !vis[x][y]);
  14. }
  15. void bfs(int x,int y){
  16. while(!q.empty()){
  17. node now = q.front();
  18. q.pop();
  19. int x1 = now.x, y1 = now.y;
  20. if(x1 == n && y1 == m){
  21. printf("Yes\n");
  22. return;
  23. }
  24. for(int i = 0; i < 4; i++){
  25. int xx = x1 + dx[i];
  26. int yy = y1 + dy[i];
  27. if(check(xx, yy)){
  28. vis[xx][yy] = 1;
  29. q.push({xx, yy});
  30. }
  31. }
  32. }
  33. printf("No\n");
  34. }
  35. int main(){
  36. char c;
  37. scanf("%d %d", &n, &m);
  38. for(int i = 1; i <= n; i++){
  39. for(int j = 1; j <= m; j++){
  40. cin >> c;
  41. if(c == '.') a[i][j] = 1;
  42. }
  43. }
  44. q.push({1, 1});
  45. vis[1][1] = 1;
  46. bfs(1, 1);
  47. return 0;
  48. }

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

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.以前我们枚举下一个点时按的是上、下、左、右的顺序枚举,而本题是按照马的走法,所以我们要重新定义偏移数组:

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

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

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

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

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

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

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

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n, m, sx, sy, a[405][405];
  4. int dx[8]={1, 2, 2, 1, -1, -2, -2, -1},
  5. dy[8]={-2, -1, 1, 2, -2, -1, 1, 2};
  6. struct node{
  7. int x, y, step;
  8. };
  9. queue<node>q;
  10. void bfs(){
  11. while(!q.empty()){
  12. node now = q.front();
  13. q.pop();
  14. for(int i = 0; i < 8; i++){
  15. int xx = now.x + dx[i];
  16. int yy = now.y + dy[i];
  17. if(xx <= n && xx >= 1 && yy <= m && yy >= 1 && a[xx][yy] == -1){
  18. a[xx][yy] = now.step + 1;
  19. q.push((node){xx, yy, now.step + 1});
  20. }
  21. }
  22. }
  23. }
  24. int main(){
  25. cin >> n >> m >> sx >> sy;
  26. for(int i = 1; i <= n; i++){
  27. for(int j = 1; j <= m; j++){
  28. a[i][j] = -1;
  29. }
  30. }
  31. a[sx][sy] = 0;
  32. q.push((node){sx, sy, 0});
  33. bfs();
  34. for(int i = 1; i <= n; i++){
  35. for(int j = 1; j <= m; j++){
  36. cout << setw(5) << a[i][j];
  37. }
  38. cout << endl;
  39. }
  40. return 0;
  41. }

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

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

3

说明/提示

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

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

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

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n, a, b, num[205], ans;
  4. bool vis[205], flag;
  5. struct node{
  6. int id, step;
  7. };
  8. queue<node>q;
  9. void bfs(){
  10. while(!q.empty()){
  11. node now = q.front();
  12. q.pop();
  13. if(now.id == b){
  14. flag = 1;
  15. ans = now.step;
  16. break;
  17. }
  18. if(now.id + num[now.id] <= n && !vis[now.id + num[now.id]]){
  19. q.push({now.id + num[now.id], now.step + 1});
  20. vis[now.id + num[now.id]] = 1;
  21. }
  22. if(now.id - num[now.id] >= 1&& !vis[now.id - num[now.id]]){
  23. q.push({now.id - num[now.id], now.step + 1});
  24. vis[now.id - num[now.id]] = 1;
  25. }
  26. }
  27. }
  28. int main(){
  29. cin >> n >> a >> b;
  30. for(int i = 1; i <= n; i++) cin >> num[i];
  31. q.push({a, 0});
  32. vis[a] = 1;
  33. bfs();
  34. if(flag) cout << ans << endl;
  35. else cout << -1 << endl;
  36. return 0;
  37. }

优化

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

练习题

我找了几道练习题,难度呈阶梯状,学完宽搜一定要做这几道题目!而且有些题目推荐用深搜和宽搜两种做法都做一遍,加深映像。

  1. P1126 机器人搬重物

  2. P1451 求细胞数量 (这题用深搜甚至更好做)

  3. P1162 填涂颜色

  4. P1807 最长路

一定要好好练习,学习完后推荐去学一下最短路算法,有弗洛伊德、Dijstra和SPFA(它没死),作为进阶训练,不过要在宽搜完全掌握后。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小丑西瓜9/article/detail/436946
推荐阅读
相关标签
  

闽ICP备14008679号