GESP 7级

BFS 层序遍历

7级 · DP/图论/搜索

📖 一句话理解

BFS（Breadth-First Search，广度优先搜索）就像往池塘扔一颗石子，水波一圈一圈往外扩散。它先访问离起点最近的所有点，再访问稍远的，用队列实现。BFS天然适合求最短路径（无权图）。
💡 为什么重要？
BFS是求无权图最短路径的标准算法。比如"迷宫最短步数""最少操作次数"等问题，BFS是首选。它也是理解图论、树的层序遍历的基础。GESP 7级中，BFS结合队列的写法是必考内容。
📋 前置知识
  • 队列（queue）：先进先出（FIFO），push入队、front取队头、pop出队
  • 基本的循环：while循环和for循环
  • 数组：用数组标记状态（如 visited[]、dist[]）

🧠 BFS的核心框架

📐 BFS标准模板
queue.push(起点);
标记起点已访问;
while (!queue.empty()) {
  int u = queue.front(); queue.pop(); // 取出队头
  for (u的每个邻居 v) {
    if (v未访问) {
      标记v已访问;
      queue.push(v);
    }
  }
}

BFS的关键点

🔑 必须理解的三件事
  1. 队列的作用：保证"先访问近的，再访问远的"。每次取出队头（最早入队的），处理它的邻居。
  2. 访问标记：visited[] 数组防止同一个点被重复访问（否则会死循环）。
  3. 层级控制：如果需要按层处理（比如层序遍历），在每次循环开始记录当前层的大小 sz = q.size()。

🔢 例1：二叉树层序遍历

💻 层序遍历代码（逐行注释）
#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
};

void levelOrder(TreeNode* root) {
    if (!root) return;              // 空树直接返回

    queue<TreeNode*> q;            // 创建一个队列，存节点指针
    q.push(root);                  // 把根节点入队

    while (!q.empty()) {           // 队列不为空就继续
        int sz = q.size();         // ⭐ 记录当前层的节点数

        for (int i = 0; i < sz; i++) {   // 遍历当前层的所有节点
            TreeNode* node = q.front();   // 取出队头节点
            q.pop();                      // 出队

            cout << node->val << " ";    // 处理当前节点（打印值）

            // 把下一层的子节点入队
            if (node->left) q.push(node->left);    // 左子节点入队
            if (node->right) q.push(node->right);  // 右子节点入队
        }
        cout << endl;  // 当前层处理完毕，换行
    }
}

🔢 例2：迷宫最短步数

给定一个N×M的迷宫，从起点走到终点，求最少步数。

💻 BFS求最短路代码
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int N = 1005;
char maze[N][N];     // 迷宫：'.'可走，'#'墙壁，'S'起点，'E'终点
int dist[N][N];       // dist[i][j] = 从起点到(i,j)的最短步数
int n, m;

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

int bfs(int sx, int sy, int ex, int ey) {
    memset(dist, -1, sizeof(dist));    // 初始化为-1，表示未访问
    queue<pair<int,int>> q;            // 队列存坐标
    q.push({sx, sy});                  // 起点入队
    dist[sx][sy] = 0;                  // 起点距离为0

    while (!q.empty()) {
        auto [x, y] = q.front();       // 取出队头坐标
        q.pop();                        // 出队

        if (x == ex && y == ey)         // 到达终点
            return dist[x][y];          // 返回最短距离

        // 尝试四个方向
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];         // 新的x坐标
            int ny = y + dy[d];         // 新的y坐标

            // 检查边界和是否可走
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (maze[nx][ny] == '#') continue;   // 墙壁不能走
            if (dist[nx][ny] != -1) continue;    // 已访问过

            dist[nx][ny] = dist[x][y] + 1;       // 距离+1
            q.push({nx, ny});                     // 入队
        }
    }
    return -1;  // 无法到达终点
}

📊 BFS vs DFS 对比

📝 什么时候用BFS，什么时候用DFS？
  • 用BFS：求最短路径（无权图）、按层处理、找离起点最近的目标
  • 用DFS：求所有方案（全排列、子集）、判断连通性、图的遍历
  • 时间复杂度：两者都是 O(节点数+边数)，但BFS空间可能更大（队列存一整层）

🚨 易错点

⚠️ 常见错误汇总
  1. 忘记标记已访问：不标记visited会导致同一个节点反复入队，死循环！
  2. 入队时就标记：visited应该在入队时标记，不是出队时！如果出队才标记，同一个节点可能在入队前被多次加入队列。
  3. 层序遍历忘记记录size：如果需要按层处理，必须在循环开始时记录 sz = q.size()，因为循环中会动态修改队列大小。
  4. pair用法不熟：BFS常用来存坐标，要熟悉 pair<int,int> 的使用。
  5. 边界检查遗漏：迷宫问题中，新坐标可能越界，必须先检查再使用。

🎯 练习建议

📝 循序渐进练习路径
  1. 先练队列操作：确保会用 queue 的 push、front、pop、empty、size。
  2. 层序遍历入门：先做二叉树层序遍历（P103、LeetCode 102）。
  3. 迷宫类题目：
    • P1443 马的遍历（洛谷经典BFS）
    • P1162 填涂颜色（BFS扩展）
    • P2895 [USACO08FEB] Meteor showers S
  4. 对比DFS：同一道题分别用DFS和BFS实现，观察结果和效率差异。
← 上一个：DFS 递归搜索 📖 返回主目录 下一个：贪心策略 →