第 12 章　图与遍历

本章解决的问题：怎么表示"事物之间的关系"？以及怎么系统地把整张"关系网"走一遍？

12.1　图的基本概念与两种存储方式

学习目标：学完本节，你能

• 说清图相对树/链表的本质区别；
• 手写邻接矩阵和邻接表两种表示，并说出各自的空间代价；
• 根据图的稠密程度选对表示方式。

先修：3.1（数组）、6.1（哈希表）、9.1（树）。 固定术语：图、顶点、边、有向图、无向图、度、邻接矩阵、邻接表。 环境与版本：.NET 8 / C# 12。 预计阅读：28 分钟。

一、直觉：从"链"到"树"到"网"

前面学过的结构，限制越来越松：

图的表达能力最强：

  链表：A → B → C → D                    一条线
  树：        A                          有层级、无环
            /   \
           B     C
  图：        A —— B                     任意连接、可以有环
             |  \  |
             C —— D

现实世界里到处都是图：

前 11 章学的所有结构，本质上都是"图的特例" —— 链表是"每个点最多连两个"的图，树是"无环 + 有向 + 单父"的图。

所以图是本书后半部分最重要的结构：它不再有那些简化的假设。

二、基本术语

三、两种存储方式

问题是：怎么把"谁和谁相连"存进计算机？

示例图（城市航线，无向图）：

        北京 —— 上海
         |  \      |
         |   \     |
       广州 —— 深圳
         |
       成都

表示法 1：邻接矩阵

用一个二维布尔数组：matrix[i][j] = true 表示顶点 i 和 j 之间有边。

var matrix = new bool[n, n];

foreach (var (a, b) in edges)
{
    int i = cityIndex[a], j = cityIndex[b];
    matrix[i, j] = true;
    matrix[j, i] = true;              // 无向图：两个方向都要标记
}

实测输出：

          北京    上海    广州    深圳    成都
  北京       ·      1      1      1      ·
  上海       1      ·      ·      1      ·
  广州       1      ·      ·      1      1
  深圳       1      1      1      ·      ·
  成都       ·      ·      1      ·      ·

1 表示有航线，· 表示没有。

注意矩阵是【对称】的 —— 因为这是无向图。

有向图就不对称了：如果只有"北京 → 上海"而没有反向，那 matrix[北京][上海] = true 但 matrix[上海][北京] = false。

表示法 2：邻接表

每个顶点记录它【直接相连】的顶点列表：

var adjList = new Dictionary<string, List<string>>();
foreach (var c in cities) adjList[c] = new List<string>();

foreach (var (a, b) in edges)
{
    adjList[a].Add(b);
    adjList[b].Add(a);                // 无向图：两个方向都要加
}

实测输出：

    北京   -> 上海, 广州, 深圳
    上海   -> 北京, 深圳
    广州   -> 北京, 深圳, 成都
    深圳   -> 北京, 上海, 广州
    成都   -> 广州

四、空间代价：差了 52 倍

这是两种表示最本质的差别。

实测（10,000 个顶点，每个平均连 10 条边）：

  实际内存占用（10,000 个顶点，每个平均 10 条边）：
    邻接矩阵:     95.4 MB   （95.4 MB = V² 个 bool）
    邻接表  :      1.8 MB   （约 V + 2E 个元素）
    矩阵是邻接表的 52.6 倍

为什么差这么多？

矩阵存了 $V^2$ 个格子，但其中只有 $2E$ 个是"有用"的（有边的）。

这个例子里，$V^2 = 10^8$，而 $2E = 10^5$ —— 有用率只有 0.1%。

99.9% 的格子是浪费的，因为它们表示"这两个城市之间没有航线"。

⚠️ 关于这个测量本身

我用了三次才把这张表测对，过程值得记录 —— 因为它暴露了"测量内存"这件事本身的陷阱：

尝试	做法	结果	问题
1	GC.GetTotalMemory 差值法	矩阵显示 0.0 MB	矩阵分配后没被"使用"，JIT 认为它已死，强制 GC 时收走了
2	加 GC.KeepAlive	邻接表显示 -94.0 MB	矩阵在测第二项时被回收，污染了结果
3	加 GC.Collect()	仍然 -94.0 MB	JIT 的存活分析与直觉不一致
4	改用 GC.GetAllocatedBytesForCurrentThread()	正确 ✓	它统计"累计分配了多少字节"，与何时回收完全无关

教训：测内存比测时间更需要小心。

• 测时间：多跑几次取最快值就能过滤噪声
• 测内存：对象什么时候被回收，取决于 JIT 的存活分析 —— 而那是你控制不了的

可靠的做法是统计"分配量"而不是"当前占用" —— 这也是 4.4 节（快慢指针判环）用过的同一招。

五、操作代价对比

  操作                           | 邻接矩阵               | 邻接表
  ----------------------------------------------------------------------
  判断两点是否相邻                     | O(1) 直接查表          | O(度数) 遍历链表
  遍历某点的所有邻居                  | O(V) 扫一整行          | O(度数) 只走有边的
  空间                             | O(V²)              | O(V + E)
  加一条边                         | O(1)               | O(1)（追加到列表）
  删一条边                         | O(1)               | O(度数)（要在链表里找）

两个关键差异：

1. 判断"两点是否相邻"：矩阵 $O(1)$，邻接表 $O(\text{度数})$

矩阵一次下标访问就知道；邻接表要遍历那个顶点的邻居列表。

2. 遍历"某点的所有邻居"：矩阵 $O(V)$，邻接表 $O(\text{度数})$

这是邻接表最大的优势 —— 也是所有图算法（DFS、BFS、Dijkstra）都会频繁做的操作。

矩阵要扫一整行（$V$ 个格子），其中绝大多数是"没有边"； 邻接表只走真正有边的那些。

六、怎么选

关键看图的【稠密程度】：

实际场景：

    - 社交网络好友关系：稀疏（平均好友数几十）-> 邻接表
    - 地图道路网络：稀疏（每个路口连 3~4 条路）-> 邻接表
    - 网页链接：稀疏 -> 邻接表
    - 小规模稠密图（比如 100 个节点的完全图）-> 邻接矩阵
    - 需要频繁判断'两点是否直接相连'-> 邻接矩阵

【结论】绝大多数真实世界的图都是稀疏图 → 默认用【邻接表】。

为什么真实世界的图大多稀疏？

因为"关系"通常是有成本的（时间、距离、注意力）。一个人不可能和几百万人都是好友，一个路口不可能通向所有其他路口。

稠密图通常只出现在"数学构造"或者"小规模"的场景里（比如 100 个城市的完全图 —— 任何两个城市都有直达航线，这在现实中不存在）。

七、邻接表用什么容器实现？

这又是一个"看起来随便选，实际有讲究"的问题。

实测（遍历全图 100 遍，10,000 个顶点，每个 10 条边）：

    List<int>[] 数组套表    :     23.1 ms
    Dictionary<int, List>   :     25.8 ms

    数组版快 1.11 倍

数组版稍快，但差距不大（1.11 倍）。

原因是：

1. 数组下标直接定位，不需要算哈希、查字典
2. 10,000 个 List 对象的引用连续排列，CPU 缓存命中率更高（3.1 节）

但要注意：这个差距很小（1.11 倍），不要为了这点性能牺牲通用性。

Dictionary 版的优势：

• 顶点编号不连续时只能用它（比如顶点是字符串 ID、或者编号是 1000, 2000, 5000...）
• 顶点动态增加时不需要扩容

实践建议：

场景	用什么
顶点编号是 0 ~ n-1 的连续整数	List<int>[]
顶点是任意类型（字符串、枚举、自定义对象）	Dictionary<T, List<T>>
顶点数是动态的	Dictionary<T, List<T>>

算法题里通常用前者（因为输入规整），工程里通常用后者（因为更灵活）。

八、练习

练习 12.1.1（画图） 把下面的邻接表还原成图（顶点编号 0~4）：

  0 -> 1, 2
  1 -> 0, 3
  2 -> 0, 4
  3 -> 1
  4 -> 2

(a) 画出这个图。 (b) 它是无向图还是有向图？ (c) 写出对应的邻接矩阵。

练习 12.1.2（计算空间） 一个图有 $V = 100{,}000$ 个顶点。 (a) 用邻接矩阵要多少内存（按 bool 1 字节算）？ (b) 如果它是稀疏图，$E = 2V$，用邻接表大约多少内存？ (c) 什么情况下才该用邻接矩阵？

练习 12.1.3（判断） 判断对错并说明理由： (a) 树是图的一种特例。 (b) 邻接矩阵比邻接表更省空间，因为它只需要一个数组。 (c) 无向图的邻接矩阵一定是对称的。 (d) 遍历一个顶点的所有邻居，邻接矩阵更快。

练习 12.1.4（工程判断） 一个打车软件要存储"道路网络"（路口是顶点，道路是边）。 (a) 这个图是稠密的还是稀疏的？ (b) 该用什么表示？ (c) 如果还要支持"实时更新路况"（边的权重变化），你的选择要改吗？

练习 12.1.5（挑战·邻接矩阵的位压缩） 邻接矩阵的一个 bool 只表示"有没有边"，用一个字节存 1 bit 信息，浪费了 7/8。

(a) 能不能用 BitArray 或者位运算把它压缩 8 倍？ (b) 压缩后，判断"两点是否相邻"还是 $O(1)$ 吗？ (c) 这样做的实际收益有多大？值得吗？

九、练习答案

12.1.1

(a) 图：

        0
       / \
      1   2
      |   |
      3   4

顶点 0 连着 1 和 2；1 连着 0 和 3；2 连着 0 和 4；3 只连 1；4 只连 2。

(b) 无向图。

判断依据：邻接表是对称的 —— 0 的列表里有 1，1 的列表里也有 0 ✓

如果是有向图，会出现"0 → 1 但 1 的列表里没有 0"这种不对称的情况。

(c) 邻接矩阵：

       0  1  2  3  4
  0    ·  1  1  ·  ·
  1    1  ·  ·  1  ·
  2    1  ·  ·  ·  1
  3    ·  1  ·  ·  ·
  4    ·  ·  1  ·  ·

验证对称性：matrix[0][1] = matrix[1][0] = 1 ✓，其余同理。

12.1.2

(a) 邻接矩阵：$V^2 = 10^{10}$ 个 bool = $10^{10}$ 字节。

$$\frac{10^{10}}{1024^3} \approx 9.3 \text{ GB}$$

约 9.3 GB —— 完全不可行。

(b) 邻接表：约 $V + 2E = 10^5 + 4 \times 10^5 = 5 \times 10^5$ 个元素。

如果每个元素占 4 字节（int）加一些列表开销，大约几 MB。

从 9.3 GB 降到几 MB —— 差了几千倍。

(c) 只有在这几种情况下才该用邻接矩阵：

最后一条值得注意：有些图算法本质上就是矩阵运算（比如求"任意两点间的最短路径"的 Floyd 算法）。这时用矩阵表示是数学上的自然选择，而不是工程妥协。

12.1.3

• (a) 对。 树是"连通、无环、每个节点最多一个父节点"的图。

  更准确地说：树是有向无环图（DAG）的一个特例，而且满足"除了根以外每个节点恰好有一个入边"。

  这个视角很有用：第 9、10 章学的树算法（遍历、查找），本质上都是图算法的特例。理解了图，树就变成了"简单的图"。

• (b) 错，反了。 邻接矩阵是 $O(V^2)$，邻接表是 $O(V + E)$。

  对稀疏图（$E \approx V$），矩阵比表多用了约 $V$ 倍的空间。

  本节实测：$V = 10{,}000$ 时，矩阵 95.4 MB vs 表 1.8 MB —— 差 52.6 倍。

• (c) 对。 因为无向边的定义就是"双向的"：A—B 意味着 A 到 B 有边，B 到 A 也有边。

  反过来也成立：如果邻接矩阵不对称，那这个图一定是有向的（或者你建图时写错了）。

  实践用途：调试图算法时，检查矩阵是否对称是验证"无向图建对了吗"的快速方法。

• (d) 错，反了。 邻接表更快。

  • 邻接矩阵：要扫一整行（$V$ 个格子），即使这个顶点只有 1 条边
  • 邻接表：只遍历这个顶点的邻居列表（$O(\text{度数})$）

  对稀疏图，这个差距是 $V$ vs 度数 —— 可能差几千倍。

  这也是"图算法要用邻接表"的核心原因：DFS、BFS、Dijkstra 全都要频繁遍历邻居。

12.1.4

(a) 稀疏图。

理由：一个路口通常只连接 3~4 条道路，而城市可能有几十万个路口。所以 $E \approx 2V$（每条边被两个路口各记一次），远小于 $V^2$。

(b) 用邻接表。

而且要带权（每条道路有长度、通行时间），所以是：

Dictionary<long, List<(long To, double Distance, double Time)>> graph;
// 或者其他等价结构：每个路口 -> 相邻路口及边的属性

注意"边带权"这一点 —— 前面讲的邻接表只存了"连到谁"，实际工程里通常还要存"这条边的属性"。

常见做法是定义一个 Edge 结构（包含目标顶点 + 权重 + 其他元数据），邻接表存 List<Edge>。

(c) 选择不用改，但实现要加东西。

"实时更新路况"意味着边的权重会频繁变化，所以要考虑：

如果改成邻接矩阵会怎样？

更新权重是 $O(1)$（matrix[i][j] = newWeight），比邻接表还快。

但空间代价是不可接受的：几十万个路口 → $V^2$ 是天文数字。

【结论】稀疏性压倒一切 —— 邻接表是唯一选择。

12.1.5

(a) 能。

用 BitArray 或者直接用 ulong[] 做位运算：

// 用 ulong[] 存位图：每 64 个顶点占一个 ulong
ulong[] bits = new ulong[(V + 63) / 64];

void SetEdge(int i, int j)
{
    int idx = i * V + j;                    // 展平成一维
    bits[idx / 64] |= 1UL << (idx % 64);
}

bool HasEdge(int i, int j)
{
    int idx = i * V + j;
    return (bits[idx / 64] & (1UL << (idx % 64))) != 0;
}

空间从 $V^2$ 字节降到 $V^2 / 8$ 字节 —— 压缩了 8 倍。

(b) 还是 $O(1)$，但常数变大了。

• 原来：一次二维数组访问（一次乘加 + 一次内存读）
• 现在：一次除法 + 一次取模 + 一次位运算 + 一次内存读

位运算比普通数组访问多了几步，但仍然是常数时间。

实际上，因为"位运算 + 缓存命中率提升 8 倍"，位图版在某些场景下反而更快（3.1 节的缓存效应）。

(c) 收益和适用性分析：

值得吗？分情况：

• $V$ 很大且图较稠密（比如 10 万个顶点的图，用矩阵要 10 GB，位图只要 1.25 GB）→ 值得
• $V$ 不大（比如 1000 个顶点，矩阵才 1 MB）→ 没必要，代码复杂度不值得
• 需要频繁"遍历邻居" → 位图不合适（逐位检查比邻接表慢得多）

位图表示在"稠密图 + 频繁判断相邻 + 不需要遍历邻居"的场景下才有价值。

一个真实的例子：布隆过滤器（Bloom Filter）就是位图思想的应用 —— 用很少的位来近似表示"某个元素在不在集合里"。

这和 6.2 节的"开放寻址用数组"、11.1 节的"堆用完全二叉树"是同一个思路：

找到数据本身的特性，用更紧凑的表示去承载它。

十、常见错误

十一、本节总结

1. 图是表达"任意关系"的结构 —— 链表和树都是它的特例。现实中的社交网络、地图、依赖关系、网页链接全是图。
2. 两种表示：邻接矩阵（$O(V^2)$ 空间，判断相邻 $O(1)$）和邻接表（$O(V+E)$ 空间，遍历邻居 $O(\text{度数})$）。
3. 实测空间差距（$V=10^4$，平均度 10）：矩阵 95.4 MB vs 表 1.8 MB，差 52.6 倍。
4. 图算法的核心操作是"遍历邻居" —— 而邻接表在这个操作上快得多（$O(\text{度数})$ vs $O(V)$）。所以默认用邻接表。
5. 真实世界的图几乎都是稀疏的（关系有成本），所以稠密图是例外而非常态。
6. 邻接表的实现：顶点编号连续用 List<int>[]（快 1.11 倍），否则用 Dictionary<T, List<T>>。差距不大，优先选通用性。
7. 测内存比测时间更容易踩坑 —— 本节实测了两次错误结果，最终改用"累计分配量"才测准。

下一节衔接：图的表示讲完了。但光有表示没用 —— 你需要能"走遍"这张网。从某个顶点出发，怎么系统地访问所有能到达的顶点？有两种基本策略：一条路走到底（DFS）和一圈一圈扩散（BFS）。它们在 9.2/9.3 节已经以"树的遍历"的形式出现过 —— 现在要推广到图上。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "12.1",
  "title": "图的基本概念与两种存储方式",
  "covered": [
    "图相对链表/树的表达能力优势与六类现实场景",
    "完整术语表（顶点/边/有向无向/度/路径/环/权重）",
    "邻接矩阵与邻接表的手写实现",
    "实测空间差距（95.4 MB vs 1.8 MB，52.6 倍）",
    "测内存的四个尝试与三次失败（0.0 MB / -94.0 MB）",
    "操作代价对比表（判断相邻、遍历邻居、增删边）",
    "稀疏图 vs 稠密图的选型判断",
    "邻接表的容器选择（List[] vs Dictionary，实测差 1.11 倍）",
    "位压缩邻接矩阵与布隆过滤器的关联"
  ],
  "unresolved": [
    "DFS 留到 12.2",
    "BFS 与最短路径留到 12.3",
    "连通分量与环检测留到 12.4",
    "Dijkstra 留到 13.3"
  ],
  "canonical_terms": {
    "图（Graph）": "由顶点和边组成的结构，表达任意关系",
    "顶点（Vertex）": "图中的节点",
    "边（Edge）": "顶点之间的连接",
    "邻接矩阵（Adjacency Matrix）": "用二维表表示图，空间 O(V²)",
    "邻接表（Adjacency List）": "用每个顶点的邻居列表表示图，空间 O(V+E)",
    "度（Degree）": "一个顶点连接的边数"
  },
  "symbols_units": {
    "V": "顶点数",
    "E": "边数"
  },
  "assumptions": [
    "读者已掌握 3.1 的数组与 6.1 的哈希表",
    "读者已读过 9.1 的树结构（图是树的推广）"
  ],
  "word_count_actual": 3180,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch12/Sec121/",
    "内存对比（95.4 vs 1.8 MB）、邻接表遍历性能（1.11 倍）均为实测",
    "练习 12.1.1 的图与矩阵已手工验证",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "测内存用了四次才做对：①GC.GetTotalMemory 差值法得 0.0 MB（对象未被使用，JIT 判定已死被回收）；②加 GC.KeepAlive 后邻接表得 -94.0 MB（矩阵在测第二项时被回收，污染结果）；③加 GC.Collect 仍无效；④改用 GC.GetAllocatedBytesForCurrentThread 才得到正确结果。已把这个踩坑过程写进正文，作为「测内存比测时间更需要小心」的教学点"
  ],
  "next": "12.2 深度优先搜索"
}