1. 宽度优先搜索 BFS (单源)#

核心思想： 从起点出发，像水波纹一样一层层向外扩散。由于其“层序”特性，在所有边权均为 1 的图中，第一次搜到目标节点时，所经过的路径一定是最短路。

核心模板：

1
void bfs() {
2
    memset(dist, -1, sizeof dist);
3
    queue<PII> q;
4
    q.push({x, y});
5
    dist[x][y] = 0; // 距离数组兼顾了标记访问的功能
6

7
    while (!q.empty()) {
8
        auto t = q.front(); q.pop();
9
        for (int k = 0; k < 8; k++) {
10
            int i = t.first, j = t.second;
11
            int nx = i + dx[k], ny = j + dy[k];
12
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue; // 越界
13
            if (dist[nx][ny] != -1) continue;                   // 已访问
14

15
            dist[nx][ny] = dist[i][j] + 1;
16
            q.push({nx, ny});
17
        }
18
    }
19
}

2. 多源 BFS#

应用场景： 图中同时存在多个起点（例如：矩阵中多个火源同时扩散，求每个点到最近火源的距离）。

初始化逻辑：

将所有起点一次性全部插入队列。
将所有起点的 dist 设为 0。
后续执行与单源 BFS 完全一致。这相当于建立了一个“虚拟源点”连接了所有实际起点。

3. 01-BFS (边权仅为 0 或 1)#

核心逻辑：

当边权不全为 1（存在 0 权边）时，普通队列不再满足单调性。使用 双端队列 (deque)：

0 权边： 目标点权重不变，优先级最高，插入队头 (push_front)。
1 权边： 目标点权重 +1，优先级较低，插入队尾 (push_back)。

注意点： 01-BFS 中，一个点可能被多次更新（如果之前通过 1 权边到达，后来发现了 0 权边路径）。虽然代码中通常用 dist[nx][ny] != -1 简写，但在某些复杂变体中，标准做法是判断 dist[nx][ny] > dist[x][y] + w。

1
int bfs01(int x1, int y1, int x2, int y2) {
2
    memset(dist, 0x3f, sizeof dist); // 初始化为无穷大
3
    deque<pair<int, int>> q;
4
    q.push_back({x1, y1});
5
    dist[x1][y1] = 0;
6

7
    while (!q.empty()) {
8
        auto [x, y] = q.front(); q.pop_front();
9
        if (x == x2 && y == y2) return dist[x][y];
10

11
        for (int k = 0; k < 4; k++) {
12
            int nx = x + dx[k], ny = y + dy[k];
13
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
14

15
            int w = (g[nx][ny] == g[x][y] ? 0 : 1);
16
            if (dist[nx][ny] > dist[x][y] + w) { // 更新最短路
17
                dist[nx][ny] = dist[x][y] + w;
18
                if (w == 0) q.push_front({nx, ny});
19
                else q.push_back({nx, ny});
20
            }
21
        }
22
    }
23
    return -1;
24
}

4. 常见应用对照表#

问题类型	核心关键词	推荐算法
迷宫/网格最短路	步数最少、边权恒为 1	单源 BFS
最近距离地图	多个起点、求到任意起点的最小值	多源 BFS
电路布线/双端搜索	开关状态切换、代价为 0 或 1	01-BFS
连通性分析	染色法、求联通块个数	BFS / DFS