图的存储：三种存法的对比与选型

vector<vector<int>> son(n + 1);
son[k].push_back(l);

1 这一章拿来练手的两个问题

给一张无向图（n 个点、m 条边，可能有自环，也可能有重边），求： ① 每个点的度数（约定：一个自环给这个点贡献 2 度）； ② 去重之后有多少条不同的边。

2 手算一遍：5 个点 7 条边，故意带上自环和重边

5 7
1 2      ┐
2 3      │
1 2      ├ 注意 1-2 出现了两次（重边）
3 3      │ 3-3 是自环
4 5      │ 4-5 和 5-4 是同一条边（也是重边）
5 4      │
1 5      ┘

• 度数： 1 号 = 两条 1-2 + 一条 1-5 = 3； 2 号 = 两条 1-2 + 一条 2-3 = 3； 3 号 = 一条 2-3 + 自环算 2 度 = 3； 4 号 = 4-5 和 5-4 两条 = 2； 5 号 = 那两条 + 1-5 = 3。
• 不同的边：{1,2}、{2,3}、{3,3}、{4,5}、{1,5} 一共 5 条。

3 3 3 2 3 / 5 —— 这组数后面每一步都会回来验。

点「运行 ▶」看结果

★ 标准答案完全绕开了「图」这个数据结构（第 20 章那条规矩）。 这一章尤其需要这一点：三种存法彼此之间很容易「一起错」—— 比如三份都忘了把无向边存两遍。所以标准答案必须来自另一个方向。

3 存法一：vector 版 —— 最好写的那种

点「运行 ▶」看结果

vector<vector<int>> g(n + 1);
g[u].push_back(v);
g[v].push_back(u);        // ★ 无向图要存两遍

4 存法二：链式前向星 —— 用数组手写的链表

点「运行 ▶」看结果

int head[N];              // head[u] = u 的第一条出边的编号，-1 = 没有
int to[2*M], nxt[2*M];    // to[e] 这条边指向谁；nxt[e] 同一个点的下一条边
int cnt = 0;

void add(int u, int v) {
    to[cnt] = v;
    nxt[cnt] = head[u];   // ★ 新边挂到链子最前面
    head[u] = cnt++;
}

遍历 u 的邻居：for (int e = head[u]; e != -1; e = nxt[e])。

它本质上就是「用数组手写的链表」：head 是每个点的链头，nxt 是 next 指针。 好处是一次性开好、零动态分配，而且内存可以精确算到字节。

边编号从 0 开始 → head 初值 -1，循环条件 e != -1     ← 本章用这种
边编号从 1 开始 → head 初值  0，循环条件 e

5 存法三：邻接矩阵 —— 查询 O(1)，代价是 n²

点「运行 ▶」看结果

三份都跑出 3 3 3 2 3 / 5。（check:viz 拿 300 组随机图验过这件事： 排序去重的暴力、三种存法、动画，五方给出同一个答案。）

⚠ 注意矩阵存的是条数（int），不是 bool —— 否则重边就没了。第 9 步细说。

6 动画：同一条边，在三种存法里各落在哪

边一条一条加进来，你能同时看到它落在矩阵的哪两格、前向星的哪两条有向边、 vector 的哪两个格子。下拉框里那三个错误版本，第 8、9 步会逐个讲。

现在看这一章的 ★：

7 ★ 先把账算出来：三个公式

点「运行 ▶」看结果

n 个点、m 条无向边：

• 矩阵存 int，一格 4 字节，(n+1)² 格；
• 前向星每条有向边要 to 和 nxt 两个 int（8 字节），无向图有 2m 条有向边 → 16m；
• ★ vector 版有个很多人想不到的开销：每个 vector<int> 的壳是 24 字节（三个指针）。 n = 100 万 时，光壳就是 24 MB —— 一条边都还没存。

跑出来的表（./cost）：

  图的样子        n          m   矩阵内存 前向星内存 vector内存   矩阵扫    表扫
  -------- -------- ----------   ---------- ---------- ----------   --------- ---------
  稀疏         1000       2000       3.8 MB    35.2 KB    39.1 KB     100 万      4000
  稀疏       100000     200000      37.3 GB     3.4 MB     3.8 MB   100.0 亿    40 万
  稀疏      1000000    2000000    3725.3 GB    34.3 MB    38.1 MB   10000.0 亿   400 万
  稠密         1000     500000       3.8 MB     7.6 MB     3.8 MB     100 万   100 万
  稠密         3000    4500000      34.4 MB    68.7 MB    34.4 MB     900 万   900 万

看第二行：n = 10 万的稀疏图，矩阵要 37 GB —— 这不是「慢」，是根本开不出来。 再看最后两行：稠密图上矩阵反而更省（表要为每条边多存 to 和 nxt 两个 int）。

8 实测：算出来的账对不对

光有公式不算数，量一遍。

稀疏图 —— ./genBig 8000（n = 8000, m = 16000，固定种子）， /usr/bin/time -v 量峰值内存（本机进程底噪约 3.9 MB，要减掉）：

算出来的和量出来的对得上（矩阵那一项 244.4 vs 244.2，误差不到千分之一）。 vector 那行比公式多一点，是因为它成倍扩容，容量常常大于实际长度。

把点数翻一倍（./genBig 16000）：

★ 点数翻倍，矩阵内存翻四倍、耗时翻五倍；两种表纹丝不动。

稠密图 —— ./genBig 2000 1000000（n = 2000, m = 100 万）：

局面完全反过来了：稀疏图上矩阵多花 50 倍内存，稠密图上它反而不吃亏。

9 ★ 存法本身会丢信息 —— 这不是打字错误

点「运行 ▶」看结果

跑出来 2 2 3 1 2（正确答案是 3 3 3 2 3）。

10 另外四种错法

点「运行 ▶」看结果

跑出来 3 1 1 1 1 —— 度数直接少一半。 这是建图最常见的错误，而且它在有向图的题上是对的（第 27 章那棵树就是）。

11 ★ 对拍：一个「顺手」的写法，一次掩盖三个 bug

300 轮实测，五个错误版本：

12 这一章可以带走的四样东西

邻接矩阵      内存 4(n+1)²        扫一遍 n²
链式前向星    内存 4(n+1) + 16m   扫一遍 2m
vector 版     内存 24(n+1) + 8m   扫一遍 2m

13 自测