BFS 广度优先搜索CSP-J

💡 核心思想

BFS 使用队列实现，按层次遍历图：先访问起点，再访问距离为1的所有点，再访问距离为2的所有点……BFS 的核心性质是：在无权图中，BFS 找到的路径就是最短路径。

🎯 直觉理解

BFS 就像水波纹——往水里扔一块石头，波纹从落点一圈一圈向外扩散。先到达离起点最近的所有点，然后是更远的点。

📝 算法流程

1. 将起点入队，标记已访问
2. 队列不空时：出队一个节点，处理它
3. 将所有未访问的邻居入队并标记
4. 记录距离/层次信息

$$d[v] = d[u] + 1 \text{，BFS保证 } d[v] \text{ 是最短距离}$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
vector<int> g[100005];
int dist[100005];
int main() {
    memset(dist, -1, sizeof(dist));
    int n, m, s; cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    queue<int> q;
    q.push(s); dist[s] = 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] << " \n"[i==n];
    return 0;
}

⚠️ 常见坑点

📚 相关题目