广度优先搜索(BFS)

1. 基本概念

广度优先搜索(Breadth-First Search, BFS)是一种图形搜索算法，从起始节点开始，沿着宽度方向探索，即先访问所有相邻节点，再访问下一层节点。

1.1 特点

  • 按层次遍历，先浅后深
  • 利用队列实现
  • 找到的路径是最短路径（在边权重相同的情况下）
  • 适合解决最短路径、最少步数等问题

2. 算法流程

2.1 基本步骤

  1. 将起始节点放入队列
  2. 标记起始节点为已访问
  3. 循环直到队列为空：
    • 出队一个节点，并处理
    • 将该节点的所有未访问相邻节点入队
    • 标记这些相邻节点为已访问

2.2 流程图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
起点 -> 入队 -> 标记已访问
      |
      v
    队列空? -> 是 -> 结束
      |
      v (否)
    出队一个节点
      |
      v
    处理当前节点
      |
      v
    找到所有未访问的相邻节点
      |
      v
    将相邻节点入队并标记为已访问
      |
      v
    返回到"队列空?"的判断

3. 代码实现

3.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
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
vector<int> graph[N];
bool visited[N];

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        
        cout << curr << " ";  // 处理当前节点
        
        for (int next : graph[curr]) {
            if (!visited[next]) {
                q.push(next);
                visited[next] = true;
            }
        }
    }
}

int main() {
    int n, m;  // n个节点，m条边
    cin >> n >> m;
    
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);  // 无向图需要双向添加
    }
    
    bfs(1);  // 从节点1开始BFS
    
    return 0;
}

3.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 <bits/stdc++.h>
using namespace std;

const int N = 1010;
vector<int> graph[N];
bool visited[N];
int prev_node[N];  // 记录前驱节点

void bfs(int start, int end) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    prev_node[start] = -1;  // 起点的前驱为-1
    
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        
        if (curr == end) break;  // 找到终点
        
        for (int next : graph[curr]) {
            if (!visited[next]) {
                q.push(next);
                visited[next] = true;
                prev_node[next] = curr;  // 记录前驱
            }
        }
    }
}

// 输出从起点到终点的路径
void printPath(int end) {
    if (prev_node[end] == -1) {
        cout << end;
        return;
    }
    printPath(prev_node[end]);
    cout << " -> " << end;
}

int main() {
    int n, m, start, end;
    cin >> n >> m >> start >> end;
    
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    bfs(start, end);
    
    if (visited[end]) {
        cout << "Path found: ";
        printPath(end);
    } else {
        cout << "No path found.";
    }
    
    return 0;
}

4. 二维网格的BFS

4.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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <queue>
using namespace std;

const int N = 100;
int grid[N][N];
bool visited[N][N];
int dist[N][N];  // 记录距离

// 四个方向：上、右、下、左
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void bfs(int startX, int startY, int n, int m) {
    queue<pair<int, int>> q;
    q.push({startX, startY});
    visited[startX][startY] = true;
    dist[startX][startY] = 0;
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        // 尝试四个方向
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 边界检查和有效性检查
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && 
                !visited[nx][ny] && grid[nx][ny] != 1) {  // 1表示障碍
                q.push({nx, ny});
                visited[nx][ny] = true;
                dist[nx][ny] = dist[x][y] + 1;
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    
    // 输入网格
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    
    int startX, startY, endX, endY;
    cin >> startX >> startY >> endX >> endY;
    
    bfs(startX, startY, n, m);
    
    if (visited[endX][endY]) {
        cout << "最短距离: " << dist[endX][endY] << endl;
    } else {
        cout << "无法到达终点" << endl;
    }
    
    return 0;
}

5. 常见应用

5.1 最短路径问题

  • 在边权重相同的图中找到两点之间的最短路径
  • 迷宫最短路径问题
  • 骑士最短路径问题

5.2 层次遍历

  • 二叉树的层次遍历
  • 网页的层次爬取

5.3 拓扑排序

  • 结合入度的BFS实现拓扑排序

5.4 双向BFS

  • 从起点和终点同时进行BFS，加速搜索过程

6. 性能分析

6.1 时间复杂度

  • O(V + E)，V为节点数，E为边数
  • 在最坏情况下，需要访问所有节点和边

6.2 空间复杂度

  • O(V)，主要用于存储访问状态和队列

7. 优化技巧

7.1 双端队列BFS

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
// 01权重BFS使用双端队列
deque<pair<int, int>> q;
q.push_front({startX, startY});
visited[startX][startY] = true;

while (!q.empty()) {
    auto [x, y] = q.front();
    q.pop_front();
    
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
            if (grid[nx][ny] == 0) {  // 权重为0的边
                q.push_front({nx, ny});  // 放到队列前端
                dist[nx][ny] = dist[x][y];
            } else {  // 权重为1的边
                q.push_back({nx, ny});  // 放到队列后端
                dist[nx][ny] = dist[x][y] + 1;
            }
            visited[nx][ny] = true;
        }
    }
}

7.2 A*搜索

结合启发式函数的BFS变体，用于加速搜索过程。

7.3 记忆化搜索

结合DP思想，避免重复状态的搜索。

8. 练习题目

  1. P1126 机器人搬重物 - 二维网格BFS的经典应用
  2. P1032 字串变换 - 类似单词接龙的字符串BFS问题
  3. P1379 八数码问题 - 经典的状态空间搜索问题
  4. P1443 马的遍历 - 骑士巡逻问题的实现
  5. P1113 杂务 - 拓扑排序问题
  6. P1825 [USACO11OPEN]玉米田迷宫Corn Maze - 带传送门的迷宫问题
  7. P1747 好奇怪的游戏 - 双向BFS实践
  8. P3395 路障 - 二维网格中的最短路径问题
  9. P1330 封锁阳光大学 - 二分图染色问题
  10. P1902 刺杀大使 - 结合二分的BFS应用

这些题目涵盖了BFS的各种应用场景

9. BFS常用模板

9.1 基础图BFS模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int N = 10010;
int n, m;               // n个点，m条边
vector<int> g[N];      // 邻接表存图
bool st[N];            // 记录是否访问过

void bfs() {
    queue<int> q;
    q.push(1);         // 从1号点开始搜索
    st[1] = true;      // 标记1号点已经被访问
    
    while(q.size()) {
        int t = q.front();
        q.pop();
        
        for(auto x : g[t]) {
            if(!st[x]) {
                st[x] = true;
                q.push(x);
            }
        }
    }
}

9.2 迷宫BFS模板

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
const int N = 110;
int n, m;              // n行m列
int g[N][N];          // 存储地图
bool st[N][N];        // 记录是否访问过
int d[N][N];          // 记录距离
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};  // 四个方向

void bfs() {
    queue<pair<int,int>> q;
    q.push({1, 1});    // 从(1,1)开始搜索
    st[1][1] = true;
    d[1][1] = 0;      // 起点距离为0
    
    while(q.size()) {
        auto t = q.front();
        q.pop();
        
        for(int i = 0; i < 4; i++) {
            int x = t.first + dx[i], y = t.second + dy[i];
            if(x >= 1 && x <= n && y >= 1 && y <= m  // 不越界
                && g[x][y] == 0                      // 不是障碍
                && !st[x][y]) {                      // 没访问过
                st[x][y] = true;
                d[x][y] = d[t.first][t.second] + 1;  // 更新距离
                q.push({x, y});
            }
        }
    }
}

9.3 最短路径BFS模板

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
const int N = 10010;
int n, m;
vector<int> g[N];
int dist[N], prev[N];  // prev记录路径
bool st[N];

void bfs(int start, int end) {
    queue<int> q;
    q.push(start);
    st[start] = true;
    dist[start] = 0;
    prev[start] = -1;  // 起点的前驱为-1
    
    while(q.size()) {
        int t = q.front();
        q.pop();
        
        if(t == end) return;  // 找到终点
        
        for(auto x : g[t]) {
            if(!st[x]) {
                st[x] = true;
                dist[x] = dist[t] + 1;
                prev[x] = t;   // 记录前驱
                q.push(x);
            }
        }
    }
}

// 打印路径
void print_path(int end) {
    if(prev[end] == -1) {
        cout << end;
        return;
    }
    print_path(prev[end]);
    cout << " -> " << end;
}

9.4 双向BFS模板

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
const int N = 10010;
int n, m;
vector<int> g[N];
queue<int> q1, q2;        // 两个队列
bool st1[N], st2[N];      // 两个访问数组
int dist1[N], dist2[N];   // 两个距离数组

int bfs() {
    q1.push(1);           // 从起点开始
    q2.push(n);          // 从终点开始
    st1[1] = st2[n] = true;
    
    while(q1.size() && q2.size()) {
        if(q1.size() > q2.size()) swap(q1, q2);  // 优化：从队列小的一端开始扩展
        
        int t = q1.front();
        q1.pop();
        
        for(auto x : g[t]) {
            if(st2[x]) return dist1[t] + dist2[x] + 1;  // 两端相遇
            if(!st1[x]) {
                st1[x] = true;
                dist1[x] = dist1[t] + 1;
                q1.push(x);
            }
        }
    }
    return -1;  // 无法相遇
}

9.5 使用建议

  1. 根据具体问题选择合适的模板
  2. 注意数组大小的定义
  3. 根据需要添加或删除相关变量
  4. 可以根据实际情况修改方向数组
  5. 注意初始化的处理

9.6 常见错误

  1. 忘记标记访问状态
  2. 数组开小导致越界
  3. 方向数组写错
  4. 边界条件判断错误
  5. 队列判空条件写错

评论区仅供交流，有问题请 联系我 反馈。