广度优先搜索 BFS：原理、图解与 C++ 实战

一、什么是 BFS

广度优先搜索（Breadth-First Search，BFS）是图和树遍历的两大基础策略之一。它的核心思想是：从起点出发，先访问所有距离为 1 的节点，再访问所有距离为 2 的节点，逐层向外扩散，像往水中投石后泛起的涟漪一样一圈圈展开。

它的两大典型应用场景是：

• 分层遍历：需要按"层"处理节点时，比如求最短层数、每层平均值、之字形层序遍历
• 无权图最短路径：因为先到的一定层数更小，BFS 第一次访问到目标时就是最短路径

1.1 BFS 与 DFS 的对比

二、核心原理与图解

BFS 的精髓在于"分层"。同一批入队的所有节点，恰好构成一层。如果在出队时记录层数，就能轻松得到每个节点到起点的距离；如果一次把当前层全部处理完再进入下一层，则称为"分层 BFS"。

2.1 BFS 分层遍历过程

以一个无向图为例，从节点 A 开始 BFS。节点编号 A-G，边连接关系如图。每一层用不同颜色标注：

2.2 队列状态变化

BFS 的执行过程就是队列的入队/出队交替。下面演示从节点 A 开始，队列在每一步的状态：

2.3 BFS 与 DFS 探索顺序对比

同样一个图，BFS 和 DFS 走出来的访问顺序差异巨大。下图展示两者在同一个图上的访问轨迹：

2.4 复杂度分析

三、通用模板

BFS 的核心结构是队列 + visited 数组。下面给出通用模板，掌握后 80% 的 BFS 题目都能套用。

3.1 基础模板（不分层）

// BFS 通用模板：求从起点 start 到达目标的最短步数
// 适用于"无权图最短路径"或"最少操作数"类问题
int bfs(vector<vector<int>>& grid, int sx, int sy) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<char>> vis(m, vector<char>(n, 0));  // 用 char 节省内存

    queue<pair<int,int>> q;
    q.push({sx, sy});
    vis[sx][sy] = 1;
    int step = 0;

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

    while (!q.empty()) {
        int sz = q.size();           // 当前层的节点数
        for (int i = 0; i < sz; ++i) {  // 处理一整层
            auto [x, y] = q.front(); q.pop();
            if (grid[x][y] == TARGET) return step;  // 找到目标
            for (int k = 0; k < 4; ++k) {
                int nx = x + dx[k], ny = y + dy[k];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if (vis[nx][ny] || grid[nx][ny] == OBSTACLE) continue;
                vis[nx][ny] = 1;       // 入队时就标记，避免重复入队
                q.push({nx, ny});
            }
        }
        step++;  // 一层处理完，步数加 1
    }
    return -1;  // 找不到
}

3.2 不分层的连通块模板

// 连通块模板：从每个未访问节点出发，BFS 把整个连通块染上色
void bfsMark(vector<vector<int>>& grid, int sx, int sy) {
    int m = grid.size(), n = grid[0].size();
    queue<pair<int,int>> q;
    q.push({sx, sy});
    grid[sx][sy] = 0;  // 直接修改 grid 充当 visited，省额外空间

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if (grid[nx][ny] != 1) continue;
            grid[nx][ny] = 0;
            q.push({nx, ny});
        }
    }
}

四、示例一：岛屿数量

题目（LeetCode 200）：给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平/垂直方向上相邻的陆地连接形成。

4.1 示例

输入：

[
  ["11110"],
  ["11010"],
  ["00000"],
  ["00011"]
]

输出：3

4.2 C++ 代码

#include <vector>
#include <queue>
using namespace std;

int numIslands(vector<vector<char>>& grid) {
    int m = grid.size(), n = grid[0].size();
    int count = 0;
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            // 发现新陆地：开始一次 BFS 把整个岛"淹掉"
            if (grid[i][j] != '1') continue;
            count++;  // 又发现一座岛

            queue<pair<int,int>> q;
            q.push({i, j});
            grid[i][j] = '0';  // 标记已访问（原地修改省空间）

            while (!q.empty()) {
                auto [x, y] = q.front(); q.pop();
                for (int k = 0; k < 4; ++k) {
                    int nx = x + dx[k], ny = y + dy[k];
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                    if (grid[nx][ny] != '1') continue;
                    grid[nx][ny] = '0';  // 入队即标记，防止重复入队
                    q.push({nx, ny});
                }
            }
        }
    }
    return count;
}

五、示例二：最短路径

题目（LeetCode 1091）：给定一个 N × N 的二进制矩阵 grid，0 表示通路，1 表示障碍。从左上角 (0,0) 出发到右下角 (N-1, N-1)，找出最短路径的长度（每步可以走 8 个方向）。如果不存在返回 -1。

5.1 思路：BFS 天然找最短

因为 BFS 是层层扩散，第一次到达目标的层数一定就是最短步数——这是无权图最短路径的标配方法。注意此题是 8 方向移动，所以方向数组要从 4 个改成 8 个。

5.2 C++ 代码

#include <vector>
#include <queue>
using namespace std;

int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    int n = grid.size();
    if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;  // 起点终点是障碍，直接无解

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

    queue<pair<int,int>> q;
    q.push({0, 0});
    grid[0][0] = 1;  // 复用 grid 存距离，起点距离为 1（包含自身）

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        int dist = grid[x][y];

        // 到达终点：当前距离即答案
        if (x == n-1 && y == n-1) return dist;

        for (int k = 0; k < 8; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (grid[nx][ny] != 0) continue;  // 非 0 = 已访问或障碍
            grid[nx][ny] = dist + 1;  // 距离 = 当前距离 + 1
            q.push({nx, ny});
        }
    }
    return -1;
}

六、示例三：单词接龙

题目（LeetCode 127）：给定两个单词 beginWord 和 endWord，以及一个字典 wordList。从 beginWord 出发，每次只能改变一个字母变成字典中的另一个单词，求从 beginWord 变到 endWord 的最短变换步数。如果不存在返回 0。

6.1 思路：把"单词"看成图节点

关键洞察是把每个单词看作图中的一个节点，两个单词只差一个字母则连一条边。问题就转化为"从 beginWord 到 endWord 的最短路径"——标准 BFS。

6.2 C++ 代码

#include <string>
#include <vector>
#include <unordered_set>
#include <queue>
using namespace std;

int ladderLength(const string& beginWord,
                  const string& endWord,
                  vector<string>& wordList) {
    unordered_set<string> dict(wordList.begin(), wordList.end());
    if (!dict.count(endWord)) return 0;  // 终点不在字典，无解

    queue<string> q;
    q.push(beginWord);
    int step = 1;  // 起点算第 1 步

    while (!q.empty()) {
        int sz = q.size();  // 当前层单词数
        for (int i = 0; i < sz; ++i) {
            string cur = q.front(); q.pop();
            if (cur == endWord) return step;  // 到达终点

            // 尝试修改每一位的每个字母
            for (int j = 0; j < cur.size(); ++j) {
                string next = cur;
                for (char c = 'a'; c <= 'z'; ++c) {
                    if (c == cur[j]) continue;  // 跳过自身
                    next[j] = c;
                    // 在字典中找到：加入下一层，并从字典删除避免重复访问
                    if (dict.count(next)) {
                        q.push(next);
                        dict.erase(next);  // 关键：入队即删除
                    }
                }
            }
        }
        step++;
    }
    return 0;  // 没找到
}

七、总结与适用场景

典型题目清单

• LeetCode 200：岛屿数量（连通块）
• LeetCode 1091：二进制矩阵最短路径（8 方向）
• LeetCode 127：单词接龙（隐式图）
• LeetCode 542：01 矩阵（多源 BFS）
• LeetCode 994：腐烂的橘子（多源 BFS 分层）
• LeetCode 207：课程表（拓扑 BFS）
• LeetCode 310：最小高度树（拓扑 BFS 剥洋葱）
• LeetCode 773：滑动谜题（状态 BFS）