红魔咖啡馆

头发越掉越多，头发越掉越少

0%

【算法】BFS

发表于 更新于 分类于 ，
本文字数： 6.2k 阅读时长 ≈ 11 分钟
介绍了广度优先搜索

BFS

参考视频1_ 参考视频2

预备知识：队列

  • 特点：先进先出（FIFO），队头删除元素，队尾插入元素

  • 基本用法：见文件

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

基本思想

解决问题

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

基本思想

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

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

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

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

基本步骤

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

空间复杂度

\(S(b^n)\)：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

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

例：奇怪的电梯

奇怪的电梯

题目描述

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

输入格式

共二行。

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

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

输出格式

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

样例 #1

样例输入 #1

1
2
5 1 5
3 3 1 2 5

样例输出 #1

1
3

提示

对于 \(100 \%\) 的数据，\(1 \le N \le 200\)，\(1 \le A, B \le N\)，\(0 \le K_i \le N\)。

本题共 \(16\) 个测试点，前 \(15\) 个每个测试点 \(6\) 分，最后一个测试点 \(10\) 分。

  • 如样例：从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
#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
No
3

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

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

  • 状态转移如图（以4 1 3为例，最后一位是次数）：

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

例：离开中山路

离开中山路

题目背景

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

题目描述

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

输入格式

第 \(1\) 行包含一个数 \(n\)。

第 \(2\) 行到第 \(n+1\) 行：整个地图描述（\(0\) 表示马路，\(1\) 表示店铺，注意两个数之间没有空格）。

第 \(n+2\) 行：四个数 \(x_1,y_1,x_2,y_2\)。

输出格式

只有 \(1\) 行，即最短到达目的地距离。

样例 #1

样例输入 #1

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

样例输出 #1

1
4

提示

对于 \(20\%\) 数据，满足 \(1\leq n \le 100\)。

对于 \(100\%\) 数据，满足 \(1\leq n \le 1000\)。

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

    对于网格地图,可以定义一个二维数组 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
/*迷宫问题如果要求最短路径（权值为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;
}