BFS

适用场景

求最短步数、迷宫最短路、层次扩展、从一个状态逐层到达其他状态。

核心思想

使用队列，先进入队列的状态先扩展，因此第一次到达某个状态时通常就是最短步数。

完整代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, start;
    cin >> n >> start;
    vector<vector<int>> g(n + 1);
    vector<int> dist(n + 1, -1);

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    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] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    for (int i = 1; i <= n; i++) cout << dist[i] << " ";
    return 0;
}

常见错误

• 入队时没有立刻标记，导致同一个点重复入队。
• 把 DFS 和 BFS 的容器混用。
• 忘记判断边界或障碍。