广度优先搜索

定义

广度优先搜索，是一种按照广度优先的顺序对「问题状态空间」进行搜索的算法。

理解

对于某些特定的问题，问题状态空间可以抽象为一张图，问题状态可以类比为节点，状态之间的联系与转换关系可以类比为图中连接节点与节点的边。使用广度优先搜索算法求解这类问题，等同于在一张图上进行广度优先遍历。

回顾深度优先搜索，其算法思想为「不撞南墙不回头」，下图展示了利用深度优先搜索求解问题的搜索过程，绿色表示已经搜索完成的状态，蓝色表示正在搜索的状态，白色表示还未搜索的状态。对于一棵搜索树，深度优先搜索会先把一个分支搜索完成（例如图中的状态 T3T_3），接着搜索其他的分支（例如图中的状态 T4T_4 以及后续状态）。

广度优先搜索，其算法思想类似「火苗传播」，下图展示了利用广度优先搜索求解问题的搜索过程，绿色表示已经搜索完成的状态，蓝色表示等待搜索的状态，白色表示还未搜索的状态。对于同一棵搜索树，广度优先搜索会先访问位于同一层的状态（例如图中的状态 T1T_1 和 T2T_2），接着访问下一层的状态（例如图中的状态 T3T_3、T4T_4、T5T_5 和 T6T_6）。

具体来说，广度优先搜索，是从初始状态开始，按照状态转移规则生成第一层后续状态，同时检查目标状态是否在这些生成的状态中。如果没有，再按照规则所有第一层生成的状态逐一拓展，得到第二层状态，并检查第二层状态中是否包含目标状态。如果没有，再按照规则拓展第三层状态。如此依次拓展并检查下去，直到发现目标状态。如果拓展完所有状态，都没有发现目标状态，则问题无解。

由于先生成的状态，一定是层数较少的，后续需要先进行拓展（状态转移），满足「先进先出」的特性，因此使用队列保存各个状态。从初始状态开始，所有拓展得到的状态都会加入一个队列，因此广度优先搜索是队列这一结构的重要应用。

广度优先搜索，适合求解最少步骤或者最短解序列等最优解问题。对于同一层的状态，其对于问题的解的价值是相同的，所以第一个找到的目标状态，一定是经过最少次数的状态转移得到的，因此必然是问题的最优解。

算法过程

广度优先搜索解决问题的过程包括三个关键因素：

  1. 状态表示：状态一般是指客观现实信息的描述，通常用 TT 表示。一般用 T0T_0 表示初始状态，即问题给出的初始条件。用 TnT_n 表示目标状态，即问题解决后的最终答案。
  2. 状态转移：根据问题给定的规则控制从当前状态转移到下一个状态。整个问题的求解过程则可以抽象为一系列的状态转移步骤，从初始状态按照特定的规则一步一步转移到目标状态。
  3. 状态判重：在大多数情况下，搜索的过程中会遇到重复状态，即现在达到的状态在之前的探索过程中已经遇到过，在这种情况下，需要注意避免死循环和空间的浪费。

代码模板

在代码层面上，广度优先搜索有最重要的两个特征：

  1. 目标状态：说明了搜索过程结束的条件，当状态转移到目标状态时，可以直接输出答案或者做其他处理，不需要进行后续的搜索。
  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
struct node{
    ... // 记录状态参数
};

void bfs(){
    queue<node> que;

    node st;
    que.push(st);// 初始状态入队

    while(!que.empty()){
        node ft = que.front(); // 每次取出队首的状态，尝试拓展
        que.pop();

        if(到达目标状态){
            ... // 输出答案或者做计数等处理
        }

        for(int i = 1; i <= 当前状态可能的转移方式数量; i++){
            if(第 i 种状态转移方式可行){
                node nxt;
                que.push(nxt); // 下一个状态入队
            }
        }
    }
    return;
}

具体应用

最短路径

有一个 N×MN \times M 方格的迷宫，迷宫里的部分方格处有障碍物，障碍物不可通过。在迷宫中移动有上下左右四种方式，每次只能从当前方格移动到与之相邻的方格。给定起点位置和终点位置，每个方格最多经过一次，问从起点到终点最短路径的长度。

问题的初始状态是人位于起点，目标状态是人通过某种移动方式到达了终点，目标状态可能有多个，最先访问到的目标状态即对应最短路径。
考虑每个步骤是从当前方格分别尝试向上、下、左、右移动一步。每次移动会有三种情况导致移动无法完成：

  1. 移动后的目标方格处于迷宫边界之外。
  2. 移动后的目标方格是障碍物。
  3. 移动后的目标方格在之前已经访问过，即违背了“每个方格最多经过一次”的题目要求。为了快速判断这种冲突，可以建立与迷宫大小相同的标志数组将已经访问过的方格进行标记。
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
int n, m;
vector<vector<int>> maze; // n * m 的迷宫，其中有障碍物的方格用 1 表示，没有障碍物的方格用 0 表示
int sx, sy; // 起点位置
int fx, fy; // 终点位置
vector<vector<bool>> vis(n, vector<int>(m, false)); // 对应迷宫各个方格的标记数组

int dir[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 使用一个数组记录向四个方向移动时横纵坐标的变化

bool check(int x, int y){ // 判断位置 (x, y) 是否位于迷宫边界之外
    if(x >= 0 && x < n && y >= 0 && y < m) return true;
    return false;
}

struct node{ // 每个状态记录当前位置的坐标 (x, y) 和从起点到达当前位置的最短路径长度
    int x, y;
    int step;
};

int bfs(){
    queue<node> que;
    node st;
    st.x = sx, st.y = sy;
    st.step = 0;
    que.push(st);
    vis[sx][sy] = 1; // 标记该位置为已经访问过
    int ans = 0;

    while(!que.empty()){
        // 每次从队首取出一个状态，并尝试拓展
        node ft = que.front();
        que.pop();

        if(ft.x == fx && ft.y == fy){ // 第一次访问到目标状态，说明找到一条最短路径
            ans = ft.step;
            break;
        }

        for(int i = 0; i < 4; i++){
            int nextx = ft.x + dir[i][0], nexty = ft.y + dir[i][1];
            // 如果当前移动不会出现三种冲突，则移动一步并继续考虑下一个位置的移动方式
            if(check(nextx, nexty) && maze[nextx][nexty] == 0 && vis[nextx][nexty] == 0){
                node nxt; // 创建下一个状态
                nxt.x = nextx, nxt.y = nexty;
                nxt.step = ft.step + 1;
                que.push(nxt);
                vis[nextx][nexty] = 1; // 标记该位置为已经访问过
            }
        }
    }
    return ans;
}

cout << bfs() << endl;

瓷砖

在一个 w×hw \times h 的矩形广场上，每一块 1×11 \times 1 的地面都铺设了红色或黑色的瓷砖。
小一同学站在某一块黑色的瓷砖上，她可以从此处出发，移动到上下左右四个相邻的、且是黑色的瓷砖上。
现在他想知道，通过重复上述移动所能经过的黑色瓷砖数。

问题的初始状态是人位于起点，每个步骤是从当前方格分别尝试向上、下、左、右移动一步。本题是一个连通问题，没有目标状态，题目需要计算的是从起点出发，能够到达的所有黑色瓷砖位置的数量。
在广度优先搜索中，从初始状态开始，搜索过程中所有合法的状态（即从初始状态经过若干次状态转移能够得到的状态），都会经历一次「入队」和一次「出队」操作。
因此，只需要从起点开始，执行一次广度优先搜索，在搜索过程中，记录「出队」的状态数量，直到队列为空，即为答案。

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
int n, m;
vector<vector<char>> maze; // 表示广场的二维数组
int sx, sy; // 记录初始位置
vector<vector<bool>> vis(n, vector<int>(m, false)); // 记录每个位置是否已经访问过的标志数组

int dir[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 使用一个数组记录向四个方向移动时横纵坐标的变化

bool check(int x, int y){ // 判断位置 (x, y) 是否位于广场边界之外
    if(x >= 0 && x < n && y >= 0 && y < m) return true;
    return false;
}

struct node{
    int x, y;
};

int bfs(){
    queue<node> que; // BFS 需要队列存储状态
    node s; // 定义初始状态
    s.x = sx, s.y = sy;
    que.push(s); // 初始状态入队
    vis[sx][sy] = 1; // 标记起点位置为已经访问过
    int ans = 0; // 记录黑色瓷砖数

    while(!que.empty()){ // 如果队列不为空，则表示还有状态可以拓展
        node ft = que.front(); // 每次从队首取出一个状态，并尝试拓展
        que.pop(); 
        ans++; // 每次从队首取出一个状态，代表从起点能到达的一个黑色瓷砖

        for(int i = 0; i < 4; i++){
            int nxtx = ft.x + dir[i][0], nxty = ft.y + dir[i][1];
            // 如果当前移动不会出现三种冲突，则移动一步并继续考虑下一个位置的移动方式
            if(check(nxtx, nxty) && maze[nxtx][nxty] == 'B' && vis[nxtx][nxty] == 0){
                node nxt; // 创建下一个状态
                nxt.x = nxtx, nxt.y = nxty; // 下一个状态的最少步数一定比当前状态多一步
                que.push(nxt); // 下一个状态入队
                vis[nxtx][nxty] = 1; // 表示对应位置为已经访问过
            }
        }
    }
    return ans;
}

cout << bfs() << endl;