BFS 基础

概念讲解

什么是 BFS？

BFS（广度优先搜索）是一种逐层搜索的算法。

BFS 特点

  • 使用队列实现
  • 保证找到最短路径（无权图）
  • 空间复杂度 O(宽度)

BFS 框架

1234567891011121314151617181920queue<State> q;
q.push(初始状态);
visited[初始状态] = true;

while (!q.empty()) {
    State cur = q.front();
    q.pop();
    
    if (到达终点) {
        处理结果;
        return;
    }
    
    for (枚举所有可能) {
        if (合法 && !visited) {
            visited = true;
            q.push(新状态);
        }
    }
}

经典应用

1. 最短路径（无权图）

1234567891011121314151617181920int bfs(int start, int end) {
    queue<pair<int, int>> q;  // {节点, 距离}
    q.push({start, 0});
    visited[start] = true;
    
    while (!q.empty()) {
        auto [u, dist] = q.front();
        q.pop();
        
        if (u == end) return dist;
        
        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push({v, dist + 1});
            }
        }
    }
    return -1;
}

2. 多源 BFS

多个起点同时开始 BFS。

12345queue<pair<int, int>> q;
for (auto& [x, y] : 起点集合) {
    q.push({x, y});
    visited[x][y] = true;
}

DFS vs BFS

特性 DFS BFS
数据结构 栈/递归 队列
最短路径 不保证 保证（无权图）
空间 O(深度) O(宽度)

考点分析

初赛考查方式

  1. 程序阅读： BFS 执行过程
  2. 编程题： 最短路径

常见考点

  • BFS 最短路径
  • 多源 BFS
  • 层序遍历

例题精讲

例题 1：最短路径

题目： 求迷宫最短路径。

解答：

BFS 逐层搜索，第一次到达终点即为最短路径。

练习题

  1. BFS 的特点是什么？
查看答案

BFS 的特点：

  1. 逐层搜索：先访问所有距离为 1 的节点，再访问距离为 2 的节点
  2. 使用队列：先进先出，保证按层序访问
  3. 保证最短路径：在无权图中，BFS 找到的路径一定是最短的
  4. 空间复杂度 O(宽度)：需要存储当前层的所有节点
  1. 什么时候用 BFS 而不是 DFS？
查看答案

使用 BFS 的场景：

  • 求最短路径：无权图的最短路径
  • 层序遍历：需要按层处理
  • 扩散问题：从多个源点同时扩散

使用 DFS 的场景：

  • 枚举所有方案：需要遍历所有可能
  • 连通性判断：判断图是否连通
  • 深度优先：需要深入探索
  1. 多源 BFS 的应用场景是什么？
查看答案

多源 BFS 的应用场景：

  1. 多起点扩散：多个源点同时扩散，求每个点到最近源点的距离
  2. 腐烂的橘子：多个腐烂橘子同时向四周扩散
  3. 地图分析：求每个陆地到最近海洋的距离

实现：将所有起点同时入队，然后正常 BFS。

易错点

⚠️ 注意：

  1. BFS 保证无权图最短路径
  2. 要先标记再入队
  3. 注意队列的空间大小
  4. 多源 BFS 要把所有起点同时入队