【算法】BFS

  • ~7.04K 字
  1. 1. BFS
    1. 1.1. 预备知识:队列
    2. 1.2. 基本思想
      1. 1.2.1. 解决问题
      2. 1.2.2. 基本思想
      3. 1.2.3. 基本步骤
      4. 1.2.4. 空间复杂度
      5. 1.2.5. 板子
    3. 1.3. 例:二叉树的层次遍历-queue的实现解释
      1. 1.3.1. 思想
      2. 1.3.2. 伪代码
    4. 1.4. 例:图的bfs
    5. 1.5. 例:奇怪的电梯
    6. 1.6. 奇怪的电梯
      1. 1.6.1. 题目描述
      2. 1.6.2. 输入格式
      3. 1.6.3. 输出格式
    7. 1.7. 样例 #1
      1. 1.7.1. 样例输入 #1
      2. 1.7.2. 样例输出 #1
    8. 1.8. 提示
      1. 1.8.1. 代码
    9. 1.9. 例:非常可乐
      1. 1.9.1. Input
      2. 1.9.2. Output
      3. 1.9.3. Sample
        1. 1.9.3.1. 输入
        2. 1.9.3.2. 输出
    10. 1.10. 例:离开中山路
    11. 1.11. 离开中山路
    12. 1.12. 题目背景
    13. 1.13. 题目描述
    14. 1.14. 输入格式
    15. 1.15. 输出格式
    16. 1.16. 样例 #1
      1. 1.16.1. 样例输入 #1
      2. 1.16.2. 样例输出 #1
    17. 1.17. 提示
      1. 1.17.1. 代码

BFS

参考视频1_ 参考视频2

预备知识:队列

  • 特点:先进先出(FIFO),队头删除元素,队尾插入元素

  • 基本用法:见文件

  • 对于bfs,我们需要一层一层遍历所有节点,那么相邻节点的访问顺序该如何确定?因此我们需要队列去存储和操作,需要使先遍历到的结点先被存储,直到当前层都被存储之后,按存储的先后顺序,先被存储的节点也会先被取出,继续遍历子节点。符合队列的FIFO特点

基本思想

解决问题

  1. 从A出发是否存在到达B的路径(DFS也行)
  2. 从A出发到达B的最短路径(DFS+剪枝也行,容易TLE)

基本思想

  • 从初始状态s(图上某个节点出发)开始利用规律,生成所有可能状态,构成树的下一层节点

  • 检查是否出现目标状态g,若未出现则对该层所有状态节点分别利用规则,生成在下一层的所有状态节点

  • 对新一层继续检查重复上述操作直到出现目标状态

  • 注意:BFS实际上是传回经过边数最少的解,因此对于所有边长度(边权)相同的情况,此时就一定是从根节点到目标节点最短的路径,BFS先找到的就一定是最短的,但如果是加权边,BFS传回的就不一定最短了。对于加权路径的最短路,我们使用Dijkstra算法求解。

基本步骤

  1. 起始:将起点(根节点)放入队列中
  2. 扩散:从队列中取出队头结点,将其相邻节点放入队列,不断重复
  3. 终止:当队列为空是,说明遍历完了所有节点

空间复杂度

:b为最大分支系数,n为树高

板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Node bfs(node source, node target){
memset(visit, 0 , sizeof(visit));
queue<node> q;
q.push(source);
visit[source] = 1;
while(!q.empty()){
Node a = q.front();
q.pop();
if (a==target) return a;
for (/*对于a所有的后继节点b*/){
if (visit[b]) continue;
q.push(b);
visit[b]=1; // 剪枝,保证节点只进队列一次
}
return NULL;
}
}

例:二叉树的层次遍历-queue的实现解释

  • 层次遍历:从上到下,从左到右进行遍历

    思想

    维护队列,用于存放节点信息,当访问到一个节点时,先访问该节点,然后将该节点的左右儿子分别入队列

    伪代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    bfs(int root){
    queue<int> q;
    q.push(root);
    while q不为空:
    获得队首元素
    队首元素出队
    输出当前节点值
    if 该节点左儿子不为空:将左儿子加入队列
    else if 该节点右儿子不为空:将右儿子加入队列
    }

    例:对于一个层次遍历:5172463的树

​ 队列q:

​ 放入root节点:q:5

​ 队列空否? 不空,输出5并删除,q:

​ 有孩子否?有,放入5的左右孩子1 7,q:1 7

​ 队列空否? 不空,输出1并删除,q:7

​ 有孩子否?有,放入1的左右孩子2 4,q:7 2 4

​ 队列空否? 不空,输出7并删除,q:2 4

​ 有孩子否?有,放入7的左右孩子6 3,q:2 4 6 3

​ 队列空否? 不空,输出2并删除,q:4 6 3

​ 有孩子否?无,继续,q:4 6 3

​ 剩下三个相同 q:6 3 q:6 q:

​

例:图的bfs

  • 图与树类似,但图任何两点间都可以有边,故方法相似
  • 但图没有层次关系,访问的是某点的邻接点,若一个点已经访问过就没必要在访问了:如B的邻接点AEC,若想要放进去子节点,则AE没有必要再入队列
  • 步骤:放入起始节点,循环判断队列空不空,若不空则放入相邻节点
  • BFS最适合的:寻找最少几步能达到目标(特殊的最短路问题)

例:奇怪的电梯

奇怪的电梯

题目描述

呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第 层楼()上有一个数字 ()。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如: 代表了 (,,……),从 楼开始。在 楼,按“上”可以到 楼,按“下”是不起作用的,因为没有 楼。那么,从 楼到 楼至少要按几次按钮呢?

输入格式

共二行。

第一行为三个用空格隔开的正整数,表示 (,)。

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

输出格式

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

样例 #1

样例输入 #1

1
2
>5 1 5
>3 3 1 2 5

样例输出 #1

1
>3

提示

对于 的数据,,,。

本题共 个测试点,前 个每个测试点 分,最后一个测试点 分。

  • 如样例:从1楼到5楼,可以从1->4->2->5 按三次按钮

  • 搜索状态:从一个状态出发,根据题目不断转移状态直到到达目标状态,对实例如图:

    如题:从1楼开始

    1楼只能往上到4楼,四楼只能往下到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
#include <iostream>
#include <algorithm>
#include <queue>
#define ios ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 300;
struct node{ // 保存按钮次数
int level; // 当前楼层
int steps; // 走到当前楼层所需要步数
}floors[N];
int n,st,ed; // 总楼层数,起始楼层,目标楼层
int a[N], vis[N]; // 分别保存每个楼层可以移动几层, 该楼层是否来过
void bfs(){
queue<node> q;
node cur, net; // 记录当前状态与下一状态
cur.level = st; // 当前位于起点,楼层为起始楼层
cur.steps = 0; // 所需步数为0
q.push(cur); // 存入根节点
vis[st]=1; // 起始已经走过,设为1;因为过去以后无需返回,返回得到的值一定更大
while(!q.empty()){ // 队列非空
cur = q.front(); // 取出队首
q.pop(); // 删掉
if (cur.level == ed){ // 如果取出的对手即为目标楼层,则可以结束
cout << cur.steps;
return ;
}
// 向上扩展
net.level = cur.level + a[cur.level] ; // 下一步可以走到哪个楼层
net.steps = cur.steps+1; // 步数加1
if (net.level<=n){ // 不超最高楼层
if (vis[net.level]==0){ // 若没有来过
vis[net.level] = 1; // 可以去 去完标记已来过
q.push(net); // 将子节点放到队列里
}
}
// 向下扩展
net.level = cur.level - a[cur.level];
net.steps = cur.steps+1;
if (net.level>=1){
if (vis[net.level]==0){
vis[net.level] = 1;
q.push(net);
}
}
}
cout << -1; // 找不到咯
return ;

}
int main(){
ios;
cin >> n >> st >> ed;
for (int i = 1; i<= n;i++){
cin >> a[i];
vis[i]=0; // 初始化
}
bfs();
return 0;
}

例:非常可乐

大家一定觉的运动以后喝可乐是一件很惬意的事情,但是seeyou却不这么认为。因为每次当seeyou买了可乐以后,阿牛就要求和seeyou一起分享这一瓶可乐,而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子,它们的容量分别是N 毫升和M 毫升 可乐的体积为S (S<101)毫升 (正好装满一瓶) ,它们三个之间可以相互倒可乐 (都是没有刻度的,且 S==N+M,101>S>0,N>0,M>0) 。聪明的ACMER你们说他们能平分吗?如果能请输出倒可乐的最少的次数,如果不能输出”NO”。

Input

三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量,以”0 0 0”结束。

Output

如果能平分的话请输出最少要倒的次数,否则输出”NO”。

Sample

输入

1
2
3
7 4 3
4 1 3
0 0 0

输出

1
2
3
No
3

  • 看似找不出图的一个搜索:只要根据信息能表示出状态,且状态能根据规则进行转移就可以用搜索

  • 定义节点状态:三杯水量+当前状态最少倒水次数

  • 状态转移如图(以4 1 3为例,最后一位是次数):

  • 目标状态:达到两个量相等一个量为0
  • 倒水要求:只能倒满或者倒空
  • 这种题目称为隐式图
  • 如何剪枝:访问过的节点不在访问

例:离开中山路

离开中山路

题目背景

《爱与愁的故事第三弹·shopping》最终章。

题目描述

爱与愁大神买完东西后,打算坐车离开中山路。现在爱与愁大神在 处,车站在 处。现在给出一个 的地图, 表示马路, 表示店铺(不能从店铺穿过),爱与愁大神只能垂直或水平着在马路上行进。爱与愁大神为了节省时间,他要求最短到达目的地距离(每两个相邻坐标间距离为 )。你能帮他解决吗?

输入格式

第 行包含一个数 。

第 行到第 行:整个地图描述( 表示马路, 表示店铺,注意两个数之间没有空格)。

第 行:四个数 。

输出格式

只有 行,即最短到达目的地距离。

样例 #1

样例输入 #1

1
2
3
4
5
>3
>001
>101
>100
>1 1 3 3

样例输出 #1

1
>4

提示

对于 数据,满足 。

对于 数据,满足 。

  • 可以使用方向数组来转移状态:

    对于网格地图,可以定义一个二维数组 int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};

    则遍历四个方向可以

    1
    2
    3
    4
    for (int i = 0; i <4; i++){
    x2 = x1+dir[i][0];
    y2 = y1+dir[i][1];
    }
  • 坑点:输入中间无空格,是一起输入的,需要用字符串转换为某行某列(ascii转化,char - 'a')存入数组

代码

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
/*迷宫问题如果要求最短路径(权值为1)相关,则可以选用bfs
这里可以将迷宫看作图,详见markdown中图的遍历
*/
#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>
#define ios ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 1010;
typedef pair<int,int> PII;
int n,sx,sy,ex,ey; // 记录地图大小,起点终点
int mmap[N][N], vis[N][N]; // 记录地图和是否走过(走过不用再往回走,不然步数一定更长)
int dx[]={-1,0,1,0}; // 方向数组x
int dy[]={0,1,0,-1}; // 方向数组y
// 结构体记录坐标与步数
struct node{
int first; // 当前x坐标
int second; // 当前y坐标
int steps; // 当前步数
};
void bfs(){
queue<node> q; // 队列
node cur, net; // 记录当前状态与下一状态
cur.first = sx, cur.second = sy, cur.steps = 0; // 初始化为起始坐标,步数为0
vis[sx][sy] = 1; // 不要忘了起始坐标设为1
q.push(cur); // 根节点入队
while(!q.empty()){ // 队列变空时搜索完毕
cur = q.front(); // 取出队首
q.pop(); // 删除队首
if (cur.first == ex && cur.second == ey){ // 到达终点
cout << cur.steps; //输出步数
return ; // 跳出
}
for (int i = 0;i <4; i++){

net.first = cur.first+dx[i]; // 下一步的x坐标
net.second = cur.second+dy[i]; // 下一步的y坐标
if (net.first<1||net.second<1||net.first>n||net.second>n) continue; // 超出边界
if (mmap[net.first][net.second]) continue; // 碰到障碍
if (vis[net.first][net.second]) continue; // 已经访问
net.steps = cur.steps +1; // 若满足前进的条件就前进一步
vis[net.first][net.second] = 1; // 把访问过的地方标记
q.push(net); // 将子节点入队列

}

}
return ;
}
int main(){
ios;
cin >> n;
string s;
// 注意:这里题目输入间没有空格,相当于是输入一整个数字,需要手动拆开
// 这里用转成字符串用ascii转化的方法
for (int i = 1;i <=n;i++){
cin >> s ;
for (int j = 1;j <=n;j++){
mmap[i][j] = s[j-1]-'0';
vis[i][j]=0;
}
}

cin >> sx >>sy >> ex >> ey;
bfs();
return 0;
}

赞助喵
非常感谢您的喜欢!
赞助喵