原始题目

下面 BFS 代码的横线处应该填什么？

void bfs(int start) {
    queue<int> q;
    q.push(start);
    dist[start] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            if (dist[v] == -1) {
                dist[v] = ___;
                q.push(v);
            }
        }
    }
}

• A. dist[u]
• B. dist[u] + 1
• C. dist[v] + 1
• D. 1

答案：B（dist[u] + 1）

BFS 的分层思想（图解）

一句话概括：u 在第 d 层，它的未访问邻居 v 必然在第 d+1 层，所以 dist[v] = dist[u] + 1。

逐项排除

队列过程模拟

注意 E 在出队时发现 H —— 这正说明扩展是按层推进的，任意时刻队列里的节点层数最多相差 1。

为什么 BFS「一发现就是最短」

1. 队列按层推进：处理完所有距离为 d 的节点，才会开始处理 d+1 的节点。
2. dist[v] == -1 保证只入队一次：第一次被到达时的层数，就是最少边数。
3. 所以在无权图（或所有边权都为 1）上，BFS 等价于 Dijkstra——这是初赛最爱考的定性结论。

复杂度

\[O(n + m)\]

每个点入队一次、每条边被检查一次（无向图检查两次，仍是 \(O(n+m)\)）。

三个易混延伸

1. DFS 不能求最短路：DFS 一条道走到黑，第一次到达不一定是最小层数，除非穷举所有路径。
2. 边权不全为 1 时 BFS 失效：要走 Dijkstra（或 01-BFS、SPFA）。
3. dist 初始化成 -1 而不是 0：0 会被当成“距离为 0”的已访问节点，导致漏判；用 -1 表示未访问。

考点总结（CSP-J/S 初赛、程序填空）

1. 程序填空见到 dist[v] == -1 → 紧跟 dist[v] = dist[u] + 1，再 q.push(v)。
2. 顺序别写反：先赋值再入队（先入队可能导致重复入队）。
3. BFS = 无权图最短路；DFS = 连通性 / 拓扑 / 回溯。
4. 队列单调性：任意时刻队列内节点层数差 ≤ 1。

思考题

如果图的边权有 1 也有 2（不全相等），BFS 还能求最短路吗？应该换成什么？