C++ 图论基础与遍历算法实战

2. BFS（广度优先搜索）

像水波扩散一样一层层往外走。适用于无权图的最短路径问题。

核心是使用队列。每次取出队头，将其未访问的邻居入队。

const int N = 1005;
bitset<N> vis;
queue<int> q;
vector<int> g[N];

void bfs(int start) {
    q.push(start);
    vis[start] = true;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        
        for (const auto& y : g[x]) {
            if (!vis[y]) {
                vis[y] = true;
                q.push(y);
            }
        }
    }
}

四、例题训练

例题一：帮派地位排名

题目逻辑： 给定一棵树（帮派关系），计算每个人的手下总数（包括间接下属）。根据手下人数降序、编号升序排序，求特定人的排名。

输入格式： 第一行 n, m。接下来 n-1 行 l r，表示 l 附属于 r。

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 1e5 + 9;
int sz[N];
vector<int> g[N];

struct Node {
    int id, siz;
    bool operator<(const Node& u) const {
        return siz == u.siz ? id < u.id : siz > u.siz;
    }
};

void dfs(int x, int p) {
    sz[x] = 0;
    for (const auto& y : g[x]) {
        if (y == p) continue;
        dfs(y, x);
        sz[x] += sz[y] + 1; // 累加子树大小
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int l, r;
        cin >> l >> r;
        g[r].push_back(l); // r 是 l 的上司
    }
    
    dfs(1, 0);
    vector<Node> v;
    for (int i = 1; i <= n; i++) {
        v.push_back({i, sz[i]});
    }
    sort(v.begin(), v.end());
    
    for (int i = 0; i < n; i++) {
        if (v[i].id == m) {
            cout << i + 1 << '\n';
            break;
        }
    }
    return 0;
}

例题二：可行路径方案数

题目逻辑： 求从起点 1 到终点 n 的最短路径方案数。由于方案数可能很大，结果对 10^9+7 取模。

关键点：

1. BFS 保证第一次到达某点的路径是最短的。
2. 使用 dp[i] 记录到达 i 的最短路径方案数。
3. 当发现更短路径时更新 dp；当发现等长路径时累加 dp。

代码实现：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
using ll = long long;

const ll N = 2e5 + 9;
const ll P = 1e9 + 7;
vector<int> g[N];
ll dp[N], d[N];

void bfs(int start) {
    queue<int> q;
    q.push(start);
    memset(d, 0x3f, sizeof d); // 初始化为无穷大
    d[start] = 0;
    dp[start] = 1;
    
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        
        for (const auto& y : g[x]) {
            if (d[x] + 1 < d[y]) {
                // 找到更短路径，更新距离和方案数
                d[y] = d[x] + 1;
                dp[y] = dp[x];
                q.push(y);
            } else if (d[x] + 1 == d[y]) {
                // 找到等长最短路径，累加方案数
                dp[y] = (dp[y] + dp[x]) % P;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    bfs(1);
    cout << dp[n] << '\n';
    return 0;
}

关于初始化的小贴士： memset(d, 0x3f, sizeof d) 是常用的技巧。因为 0x3f 填充后每个 long long 约为 4.5e18，远大于最大路径长度，且不会溢出，适合作为'无穷大'使用。如果初始化为 0，会导致距离比较逻辑失效。