广度优先搜索（BFS）

广度优先搜索使用先进先出队列，从起点开始一层一层扩展。第 0 层是起点，第 k 层包含所有最少经过 k 条边可达的结点。因此，在无权图或每条边权都为 1 的图中，BFS 能求单源最短路。

1. 无权图最短路模板

dist[v] == -1 表示未访问。当从 u 第一次发现 v 时，立刻设置距离并入队；此时得到的距离已是最短距离。访问标记必须在入队时完成，不能等到出队。

vector<vector<int>> g(n + 1);
vector<int> dist(n + 1, -1), parent(n + 1, -1);
queue<int> q;

dist[s] = 0;
q.push(s);
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : g[u]) {
        if (dist[v] != -1) continue;
        dist[v] = dist[u] + 1;
        parent[v] = u;
        q.push(v);
    }
}

若目标为 t，可沿 parent[t] 不断回溯至 s 来恢复路径，最后再反转该序列。

2. 网格与状态空间 BFS

迷宫中每个可走格子都是一个状态，四个方向移动构成边。数组下标必须先判断边界，再访问；不同状态可以是坐标、字符串、棋盘布局或多个变量的组合。

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
queue<pair<int, int>> q;
dist[sx][sy] = 0;
q.push({sx, sy});

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 (!inside(nx, ny) || wall(nx, ny) || dist[nx][ny] != -1) continue;
        dist[nx][ny] = dist[x][y] + 1;
        q.push({nx, ny});
    }
}

3. 常用变形

多源 BFS：将所有起点的距离置为 0 并同时入队，得到每个点到最近起点的距离。双向 BFS：从起点和终点同时扩展，适合状态空间很大且目标明确的问题。边权只有 0 或 1 时，应使用双端队列实现 0-1 BFS；一般正权最短路则使用 Dijkstra，而不是普通 BFS。

4. 复杂度与易错点

邻接表 BFS 的时间复杂度为 O(V + E)，队列、距离和前驱数组额外占 O(V) 空间；邻接矩阵实现需要 O(V²) 时间。网格 BFS 的复杂度与实际访问格子数及每格转移数成正比。

不要遗漏起点初始化；不要重复入队；若题目有多个起点，必须全部先入队；若要求最短路，普通 BFS 只适用于无权或等权为 1 的边。