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

三、图的遍历

1. DFS（深度优先搜索）遍历图

通俗的讲，就是'一条路走到黑'。

const int N = 1000;
bitset<N> vis; // vis[i]=true 表示该点已走过
vector<int> g[N];

void dfs(int x) {
    vis[x] = true; // 给该点打上标记
    for (const auto y : g[x]) {
        if (vis[y]) continue;
        dfs(y);
    }
}

2. BFS（广度优先搜索）遍历图

就是'一层层往外走，每个点只走一次'。

核心思想是：从起点出发，先访问起点的所有直接邻接节点（第一层），再依次访问每个邻接节点的邻接节点（第二层），以此类推，直到遍历完所有可达节点。

形象理解：像'水波扩散'一样，从起点向外逐层覆盖，能保证第一次到达某个节点时的路径是最短路径（适用于无权图 / 边权为 1 的图）。

需要用队列，代码：

bitset<N> vis; // vis[x]=true 说明已经走过
queue<int> q; // 表示待拓展的点队列

while (!q.empty()) {
    // 步骤 1：取出当前队头节点 x，并从队列中移除
    int x = q.front();
    q.pop();
    
    // 步骤 2：如果 x 已访问过，直接跳过后续逻辑
    if (vis[x]) continue;
    
    // 步骤 3：标记 x 为已访问
    vis[x] = true;
    
    // 步骤 4：遍历 x 的所有邻接节点 y
    for (const auto& y : g[x]) {
        // 步骤 4.1：将 y 入队（核心操作）
        q.push(y);
    }
}

详细图解：

// bfs 详细理解：
// 1
// / \ 
// 2 3
// \ /
// 4

• 起点 1 入队，vis[1]=true
• 队列变为 [1]
• 弹出队头 1，遍历其邻接节点 2、3：
  • 2 未访问 --> vis[2] = true + 入队；
  • 3 未访问 --> vis[3] = true + 入队；
  • 队列变为 [2, 3]
• 处理 2：弹出队头 2，遍历其邻接节点 4：
  • 4 未访问 --> vis[4] = true + 入队；
  • 队列变为 [3, 4]
• 处理 3：弹出队头 3，遍历其邻接节点 4：
  • 4 已访问（vis[4] = true）--> 跳过；
  • 队列变为 [4]

四、例题训练

例题一：帮派弟位

问题描述

有一个帮派，小明不学无术，混入其中。给定一个正整数 n，代表该帮派的总人数，并且小明的序号是 m，给出这 n 个人中每个人的附属关系，确保给出的关系网为一棵树。帮派地位的定义是按照自己手下有多少帮众决定的，注意手下的手下也算是自己的手下。如果手下的帮众相同则按序号较小的在前面。你能帮助小明找到自己的帮派地位吗？

输入格式

第一行，两个正整数 n (1≤n≤10^5) 和 m (1≤m≤n)，代表该帮派的总人数以及小明的序号。 接下来 n−1 行，每行两个正整数，格式如下：

• l r (1≤l,r≤n)，代表序号为 l 的人附属于序号为 r 的人。

输出格式

一行，包含 1 个正整数，输出按手下人数多少排序后小明的排名。

样例输入

6 4
2 1
3 1
4 2
5 2
6 5

样例输出

5

代码详解

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

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

// 题目逻辑：其实就是 dfs 求 size 子树大小 -1
// 最终可得：
// 1 5（1 有 5 个小弟，1 为第一关键字，5 为第二关键字）
// 2 3
// 3 0
// 4 0
// 5 1
// 6 0
// 然后按第二关键字降序，第一关键字升序排序：
// 5 3 1 0 0 0
// 1 2 5 3 4 6 --->小明是编号 4，他排行 5，所以答案输出 5

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; // 要加一，不然全是 0
    }
}

// 改写 sort 规则
struct Node {
    int id, siz;
    bool operator<(const Node &u) const {
        return siz == u.siz ? id < u.id : siz > u.siz;
    }
};

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.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';
        }
    }
    return 0;
}

例题二：可行路径的方案数

问题描述

有 n 个城市，这些城市间有 m 条双向路径，第 i 条路径连接城市 ai 和城市 bi，通行时间为 1 小时。请问 1--->n 有多少种可行路径？由于答案可能非常大，因此将答案对 10^9+7 取模。

输入格式

第一行包含两个整数 n 和 m。 接下来 m 行，每行包含两个整数 ai 和 bi，表示存在一条连接城市 ai 和城市 bi 的双向路径。 数据范围保证：2≤n≤2×10^5，0≤m≤2×10^5，1≤ai<bi≤n。

输出格式

输出一个整数，表示最快到达目的地的城市的方案数，答案对 10^9+7 取模。

输入样例

4 4
1 2
1 3
3 4
2 4

输出样例

2

代码详解

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

/* 先建图，bfs 第一次走到终点时的距离一定是最近距离，设 dp[i] 表示从 1 到 i 的最近距离的路径方案数，在 bfs 过程中 A->B 更新 d[B](即 B 到 1 点的最近距离) */
// d[B]=min(d[B],d[A]+1),如果距离变小了。就重新计算 dp[B]=dp[A],否则就 dp[B]+=dp[A]。
// d[i] 指的是索引城市 i 到 1 的最近距离！dp[i] 指的是 i 到 1 的最短路径数（方案数）！
// 一定要注意是两个最近！
const ll N = 2e5 + 9;
const ll P = 1e9 + 7;
vector<int> g[N];
ll dp[N], d[N];

void bfs(int x) {
    bitset<N> vis;
    queue<int> q;
    q.push(1);
    memset(d, 0x3f, sizeof d); // 初始化 d 无穷大！
    d[1] = 0; // 初始化 1 到 1 的距离是 0
    // 在此题目城市间的距离默认为 1
    dp[1] = 1; // 初始化 1 到 1 的路径方案数为 1
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        if (vis[x]) continue;
        vis[x] = true;
        for (const auto &y : g[x]) {
            // 情况 1：从 1 到 x 再到 y 的路径长度（d[x]+1）比已知最短距离 d[y] 长 --> 不是最短路径，跳过
            if (d[x] + 1 > d[y]) continue;
            // 情况 2：从 1 到 x 再到 y 的路径长度等于已知最短距离 d[y] --> 找到新的最短路径，累加路径数
            else if (d[x] + 1 == d[y]) dp[y] = (dp[x] + dp[y]) % P;
            // 情况 3：从 1 到 x 再到 y 的路径长度比已知最短距离 d[y] 短 --> 更新最短距离和路径数
            else {
                d[y] = d[x] + 1; // 更新最短距离
                dp[y] = dp[x]; // 路径数继承自 x（此时 x 是第一条最短路径的前驱）
                q.push(y); // 最后两个条件满足其一就入栈
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.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 的说明

memset(d, 0x3f, sizeof d) 的作用：

1. 为什么需要这行代码？ d[i] 表示「城市 i 到起点 1 的最短距离」，初始化时需要给所有节点的最短距离赋一个极大值（无穷大）。原因是初始状态下，我们只知道起点 1 到自己的距离是 0（d[1]=0），其他节点到 1 的距离是未知的，默认设为'无穷大'表示「尚未找到路径」。BFS 过程中，当第一次通过节点 x 到达节点 y 时，d[x]+1 一定小于 d[y]（因为 d[y] 是无穷大），此时才能正确更新 d[y] = d[x]+1（标记为第一条最短路径）。
2. 0x3f 是什么？ memset 是按字节赋值的函数，0x3f 是十六进制数，对应的十进制是 63，二进制是 00111111；d 数组的类型是 ll（long long，8 字节），memset(d, 0x3f, sizeof d) 会给 d 中每个字节都赋值为 0x3f，因此每个 ll 类型的 d[i] 的值为：0x3f3f3f3f3f3f3f3f（8 个 0x3f 拼接），对应的十进制约是 1e18，远大于题目中 n≤2e5 的最大可能距离（最长路径最多 2e5 步），是一个安全的'无穷大'。
3. 为什么不用 memset(d, 0, ...) 或其他值？ 若初始化为 0：d[y] 初始为 0，而 d[x]+1 ≥ 1，会导致 d[x]+1 > d[y] 永远成立，无法更新任何节点的距离，逻辑完全错误；若初始化为其他小值（比如 1e9）：虽然也能作为'无穷大'，但 0x3f3f3f3f3f3f3f3f 是 memset 能赋出的、适合 long long 的最优极大值（不会溢出，且足够大）。