图的表示

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. 表示方式不是实现细节

图是一个抽象对象：一组顶点和边，仅此而已。计算机无法存储抽象对象。它存储的是字节，而选择哪些字节，在你写下一行算法之前，就已经决定了你的程序能做到什么。

这个论断很容易说出口，也很容易被低估，所以下面是它最锋利的版本。广度优先搜索在邻接表上的运行时间是 O(n + m) ，在邻接矩阵上则是 O(n2) 。同样的算法，同样的图，同样的输出，唯一不同的是存储方式。在一个有一百万个顶点和五千万条边的图上，这就是大约 5100 万次操作与大约一万亿次操作之间的差别：相差约 19,600倍。再怎么调优常数因子也补不回来。表示方式从一开始就是这个算法的渐近复杂度。

看破之后原因很简单。两个版本的 BFS 在每个顶点上做的是同一件事：枚举它的邻居。邻接表回答“ v的邻居有哪些？”所花的时间与邻居的数量成正比。邻接矩阵则通过扫描一整行长度为 n的数据来回答，而其中大部分是零。对所有顶点求和，邻接表的开销是 2m ，矩阵的开销是 n2。正是这一观察，让 Hopcroft 和 Tarjan 在 1970 年代初建立起线性时间的图算法，也正因如此，此后每一门算法课都把邻接表当作默认选择。

但邻接表并不总是答案，把它当成自动的默认选择本身也是一个错误。问两个给定顶点是否相邻，矩阵一次内存访问就能回答，而邻接表要扫描一段邻居序列。把图和自身相乘，矩阵会免费给出途径的数目。存储一个真正稠密的图，矩阵用的内存更少，而不是更多。要在 GPU 上运行，两种结构都不是你想要的。

所以诚实的提法不是“哪种表示最好”，而是你最常问的是哪个问题，以及这个图有多大。本文逐一讲解实践中重要的七种表示，推导每种表示上每个操作的开销，并以一套决策流程收尾。下面这个示例图的每个数字都是脚本算出来的，而不是断言出来的，计算过程也一并给出，方便你核对。

2. 贯穿示例

一个小小的带权图撑起了整篇文章。它被刻意做得足够小，以便在每种表示中都能完整写出来；又被刻意做得足够不规则，以便各种表示看起来确实不同。

V = {0, 1, 2, 3, 4, 5}

E = { {0,1}:4   {0,2}:3   {1,2}:2   {1,3}:5   {2,4}:7   {3,4}:1   {3,5}:6 }

n = 6      m = 7      度之和 = 14 = 2m
各顶点的度  0:2   1:3   2:3   3:3   4:2   5:1

关于它的两个事实会反复出现。它按升序写出的邻居集合是

0 → 1, 2
1 → 0, 2, 3
2 → 0, 1, 4
3 → 1, 4, 5
4 → 2, 3
5 → 3

，它的密度是 7 / 15 = 46.7%，因为一个有 6 个顶点的简单图最多容纳 C(6,2) = 15 条边。按真实世界的标准，这非常稠密，而这正是一个有用的纠正：教科书中的玩具图几乎总是稠密的，它们所建立的关于表示方式的直觉，对生产数据几乎总是错的。我们会在第 6 节中纠正这一点。

3. 边列表

最简单的表示方式，就是把各条边写下来，然后就没了。

edges = [ (0,1,4), (0,2,3), (1,2,2), (1,3,5), (2,4,7), (3,4,1), (3,5,6) ]

一个包含 m 个三元组的数组。如果你同时保存顶点数，空间是 Θ(n + m) ；如果顶点集隐含在边中，空间是 Θ(m) 。什么都不预先计算，什么都不建索引。

后果是几乎每次查询都要完整扫描一遍。“1 和 4 相邻吗？”需要走遍全部七条边。“3 的邻居有哪些？”同样需要走遍全部七条边。两者都是 O(m)，如果你把它放进一个对顶点的循环里，那就是灾难，因为这会变成 O(nm)。

然而边列表并不是一个幼稚的选择，因为有三种重要的场景恰好需要这种形态：

• 在边上而不是在顶点上迭代的算法。 Kruskal 算法按权重对所有边排序并依次考察它们，它从不索要邻居列表。Bellman-Ford 把每条边松弛 n - 1 次，同样是纯粹的边迭代。对这些算法来说，边列表不只是够用，而是最优的，因为任何其他表示都得先摊平回边的顺序。
• 交换与存储。磁盘上的每一种图文件格式都是边列表，因为它是唯一一种与顺序无关、只需追加且解析起来毫不费力的表示。当你从 SNAP 或 DIMACS 数据集下载数据时，拿到的就是边列表，而你的第一步就是把它转换掉。
• 流式处理。如果图根本装不进内存，到来的就是边列表，一次一条边，而半流式计算模型正是建立在“你只能拿到这些”的假设之上。

实用的规律是：边列表是一种传输格式和迭代格式，而不是查询格式。真实系统读入边列表后会立刻构建出带索引的结构。这个转换是第 7 节的主题，而且它比人们预想的便宜：按顶点编号做一次计数排序即可完成，用时 O(n + m)。

4. 邻接矩阵

把顶点编号为 0 到 n - 1 ，并构建 n × n 矩阵 A ，其中 A[u][v] = 1 当且仅当 {u, v} 是一条边，否则为 0 。对贯穿示例来说：

      0  1  2  3  4  5        行和
  0 [ 0  1  1  0  0  0 ]         2
  1 [ 1  0  1  1  0  0 ]         3
  2 [ 1  1  0  0  1  0 ]         3
  3 [ 0  1  0  0  1  1 ]         3
  4 [ 0  0  1  1  0  0 ]         2
  5 [ 0  0  0  1  0  0 ]         1

36 个单元格，其中 14 个非零

有三条结构性质可以直接读出，而且每一条在调试时都是可用的检查手段。

• 无向图的矩阵是对称的。 A[u][v] = A[v][u] 始终成立，因此有一半的存储是冗余的。有向图放弃了这种对称性，而这恰恰使方向在代数中变得可见。
• 各行之和就是各顶点的度： 2、3、3、3、2、1，与第 2 节中的列表一致。1 的总个数是 2m = 14，因为每条边占据两个单元格。
• 对角线为零（对于简单图而言），因为非零的对角线元素就是一个自环。

你买到的是常数时间的相邻性判断。问 1 和 4 是否相邻只需一次数组读取，即 A[1][4]，与度无关。本文中没有别的表示能在不借助哈希的情况下做到这一点。你付出的代价是 Θ(n2) 的空间，无论实际有多少条边，以及 Θ(n) 的时间来枚举一个顶点的邻居，无论它的邻居有多少。

最后这项代价才是真正咬人的。顶点 5 只有一个邻居，但为了发现这一点而读取第 5 行要触及六个单元格。把规模放大到一百万个顶点，找出一个度为一的顶点的邻居就要触及一百万个单元格。矩阵版 BFS 中的 O(n2) ，完全就是这个效应累积起来的结果。

位压缩这一改进。如果图是无权的，每个单元格只需要一个比特，而不是一个字节，更不是一个 32 位整数。把每一行打包进机器字，相对字节矩阵能把内存减少到八分之一，相对整型矩阵减少到三十二分之一，而且还带来一件更有意思的事：它让你每条指令就能处理 64 个邻居。求两个邻域的交集，也就是三角形计数和许多团算法的内层循环，会变成按字进行的 AND 运算，作用于 n/64 个字，而不是对 n 个元素逐一循环。我们会在第 11 节回到这一点，因为这正是稠密表示得以存活的主要原因。

5. 邻接表

为每个顶点存储一个由它的邻居组成的序列。

adj[0] = [ (1,4), (2,3) ]
adj[1] = [ (0,4), (2,2), (3,5) ]
adj[2] = [ (0,3), (1,2), (4,7) ]
adj[3] = [ (1,5), (4,1), (5,6) ]
adj[4] = [ (2,7), (3,1) ]
adj[5] = [ (3,6) ]

空间是 Θ(n + m)：每个顶点一个槽位，再加上 2m = 14 个邻居条目（无向图），或 m 个（有向图）。枚举 v 的邻居的开销是 Θ(deg(v))，这是最优的，因为你不可能列出 k 个东西却用不到 k 的时间。

正是这种表示让线性时间的图算法成为可能，而它被广泛采用有一段确切的历史。Tarjan 1972 年关于深度优先搜索的论文，以及 Hopcroft 和 Tarjan 1973 年的配套算法，都明确指出 O(n + m) 的界依赖于以邻接表方式存储；同样的过程在矩阵上是 O(n2)。此后 Aho、Hopcroft 和 Ullman 1974 年的教科书把邻接表定为标准讲法，从那时起它就是遍历代码中的默认选择。

代价是相邻性判断不再是常数时间。要回答“1 和 4 相邻吗？”，你得扫描 adj[1]，三个条目，却什么也没找到。一般来说这是 O(deg(u))，如果你足够细心去扫描较短的那个列表，则是 O(min(deg(u), deg(v))) 。在一个存在少数超高度顶点的图上，也就是任何社交图或网页图的样子，这个最小值仍可能是数百万。

邻居顺序的问题。定义中没有任何地方说邻居序列必须有序，大多数代码就让它们保持插入顺序。把它们排序一次的开销是 O(m log m) ，换来两样东西：可二分查找的相邻性判断，用时 O(log deg(u))；以及通过归并在线性时间内求邻域交集，而快速的三角形计数实现正是依赖于此。只要你会求邻域交集，就排序。

实现上的陷阱。教科书里邻接表的形象是一个链表数组，而在现代硬件上，这个形象是个糟糕的建议。链表每个邻居都要解引用一个指针，而每次解引用都可能是一次缓存未命中，代价大约上百个周期。 vector<vector<int>> 会更好，因为每个顶点的邻居是连续的，但它仍然把 n 个单独分配的内存块散落在堆上，并且每个顶点都要付一份分配头部的开销。解决办法见第 7 节。

基于哈希的变体。把每个邻居序列换成哈希集合，相邻性判断的期望开销为 O(1) ，同时空间仍保持为 Θ(n + m) ，看起来两全其美。在实践中常数并不友好：哈希集合的内存开销是紧凑整型数组的数倍，会破坏迭代的局部性，还会让邻居扫描，也就是你最常做的操作，明显变慢。只有当相邻性查询确实比遍历更占主导时才用它，并且要测量而不是想当然。

6. “稀疏”究竟意味着什么

上面的一切都系于一个词。图是稀疏的，指 m 接近 n ；图是稠密的，指 m 接近 n2。实用的分界线是密度

密度 = m / C(n,2) = 2m / (n(n-1))

也就是实际存在的边占所有可能边的比例。贯穿示例处在 7/15 = 46.7%，这极其稠密。真实的图并非如此。一个有一百万用户、五千万条好友关系的社交网络，平均每人 100 个好友，密度为 1.0 × 10-4：万分之一。道路网络更极端，平均度不到 3，因为一个路口的道路数量有限。网页图、引文图、蛋白质相互作用网络和依赖图都处在同一个量级。

下面是这样做的代价，针对的正是那个一百万顶点的图：

即便压到每格一比特，矩阵仍比稀疏结构大约大 300 倍，而且它装不进任何一台普通机器的内存。这不是边缘性的偏好，而是一个程序能运行和根本无法启动之间的差别。

这个临界点值得精确掌握。位压缩矩阵的开销是 n2/8 字节；每条有向弧存储一个 4 字节目标的稀疏结构，开销约为 8m 字节。当 n2/8 < 8m时矩阵胜出，也就是当 m > n2/64时，对应的密度约为 3.1%以上。在此之上用矩阵，在此之下就别用。除了小规模的组合搜索问题，你会遇到的几乎所有图都比这个界低三个数量级。

完整的逐项操作对比，其中 d 表示所涉顶点的度：

基本就是这种形式的这张表是标准讲法，可追溯到 Aho、Hopcroft 和 Ullman，并在 Cormen、Leiserson、Rivest 和 Stein 的图论章节中重现。请把它读作关于你问的是哪个问题的陈述，而不是关于哪一行最好。矩阵独占优势的唯一单元格是相邻性判断，边列表占优的唯一单元格是整边迭代和追加。其余一切都属于带索引的稀疏结构。

7. 压缩稀疏行

生产环境中的图代码真正使用的表示方式，并不是向量数组形式的邻接表，而是压缩稀疏行（CSR），它原封不动地借自稀疏线性代数：自 1970 年代初 Gustavson 的工作以来它就是标准做法，Duff、Erisman 和 Reid 把它记录为规范的稀疏存储方案。图论领域的人有时称之为 forward star 表示，或者干脆叫作摊平的邻接表。

思路是把所有邻居序列拼接成一个数组，再用第二个数组记录每个顶点的那一段从哪里开始。

offsets = [ 0, 2, 5, 8, 11, 13, 14 ]                       长度 n + 1 = 7
targets = [ 1, 2, 0, 2, 3, 0, 1, 4, 1, 4, 5, 2, 3, 3 ]     长度 2m  = 14
weights = [ 4, 3, 4, 2, 5, 3, 2, 7, 5, 1, 6, 7, 1, 6 ]     长度 2m  = 14

顶点 v 的邻居是 targets[offsets[v] .. offsets[v+1] - 1]。对顶点 2 来说是第 5 到第 7 个位置，得到邻居 [0, 1, 4] ，权重为 [3, 2, 7]，与 adj[2] 完全一致。度也可以免费得到，即 offsets[v+1] - offsets[v]，无需触碰目标数组就能还原出 2、3、3、3、2、1。

从渐近意义上说它与邻接表完全相同。但在实践中它要快得多，原因有四，都与大 O 无关：

• 局部性。一个顶点的邻居占据连续的字节，因此扫描它们是在缓存行中顺序流动，而不是到处追指针。硬件预取器能看出这种访问模式并始终领先一步。
• 没有按顶点的分配。两次分配取代了 n + 1 次分配。在一百万顶点的例子中，这省掉了约 38 MiB 的分配头部，更重要的是，消除了邻居块被打散的一百万次机会。
• 序列化毫不费力。整个结构就是两个整数数组，因此可以从磁盘做内存映射、通过网络发送，或者直接交给 GPU，无需修正指针。
• 索引压缩。由于 targets 存储的是顶点编号，顶点数少于 2³² 的图每个条目只需 4 字节，少于 2¹⁶ 的只需 2 字节。不过一旦 2m 超过 2³¹，偏移数组就必须使用 64 位条目，这在十亿条边的规模上是真实存在且经常犯的错误。

从边列表构建 CSR 的开销是 O(n + m) ，而且不需要排序。一趟遍历统计每个顶点的度，把计数做前缀和存入 offsets，然后第二趟用每个顶点一个的移动游标，把每条边放到它的位置上。这就是按源顶点做计数排序，也是每个严肃的图库的标准导入路径。

代价是僵硬。插入一条边会使 targets中其后的每个条目都要移动，因此这个结构实际上不可变：你需要花 Θ(n + m) 重建它，而不是更新它。当图加载一次、查询多次时，这是一笔划算的交易，大多数分析型负载都是如此；而当图不断变化时，这笔交易就很糟。第 12 节处理第二种情况。

8. 关联矩阵

第三种经典矩阵用顶点对边建立索引，而不是对顶点。把七条边标为 e1 到 e7 （按列出的顺序），并令 B[v][e] = 1 ，当且仅当 v 是 e的端点：

       e1 e2 e3 e4 e5 e6 e7
   0 [  1  1  0  0  0  0  0 ]
   1 [  1  0  1  1  0  0  0 ]
   2 [  0  1  1  0  1  0  0 ]
   3 [  0  0  0  1  0  1  1 ]
   4 [  0  0  0  0  1  1  0 ]
   5 [  0  0  0  0  0  0  1 ]

各列之和均为 2      各行之和 2,3,3,3,2,1 = 各顶点的度

它的形状是 n × m，因此空间是 Θ(nm)，对于任何边数多于顶点数的图，都比邻接矩阵更差。没有人会为了计算而这样存储图。关联矩阵之所以有一席之地，是另一个原因：它是图论与线性代数之间的桥梁。

两个恒等式说明了这一点。对上面的无符号矩阵， B BT = A + D，其中 D 是由各顶点的度构成的对角矩阵。代入贯穿示例的数字可以精确验证。如果你改为定向每条边（方向任意），在尾端写 -1 ，在头端写 +1 ，那么带符号关联矩阵 Bs 满足

B_s B_s^T  =  D - A  =  L,   即拉普拉斯矩阵

与你选择的定向无关。正是这个恒等式使拉普拉斯矩阵半正定，它也是通往谱图论的入口。Diestel 沿着这条线继续展开，用关联矩阵定义图的环空间和割空间，它们是二元域上的两个向量空间，维数分别为 m - n + c 和 n - c （对于有 c 个连通分量的图）。关联矩阵也是流问题的天然框架：网络流线性规划的约束矩阵就是带符号关联矩阵，而它的全幺模性保证了该线性规划存在整数最优解。

还有一点。关联矩阵处理多重图比邻接矩阵更优雅，因为平行边只是不同的列，而不是塞进一个单元格里的计数。超图中一条边可以连接两个以上的顶点，它根本没有合理的邻接矩阵，却有一个完全自然、列和大于二的关联矩阵。如果你需要推广到普通图之外，这就是可以推广的那种表示。

9. 方向、权重、重数与自环

到目前为止都假设的是简单无向图。四种常见的偏离会改变每种表示必须做的事，而这些差异正是实现缺陷聚集的地方。

方向。在有向图中，邻接矩阵不再对称， A[u][v] = 1 只表示一条从 u 到 v 的弧。邻接表把每条弧存一次而不是两次，因此邻居数组存放 m 个条目，而不是 2m个。这种减半是内存估算差出两倍的最常见原因。

真正的麻烦在于有向图有两种邻域。 adj[v] 给出后继；前驱则要么扫描整个结构，要么存储一份所有弧都反向的副本。稀疏线性代数把这第二份副本称为压缩稀疏列（CSC），任何需要反向行走的算法，包括反向可达性、Kosaraju 的强连通分量算法，以及双向搜索中反向运行的 Dijkstra ，都需要它。请按两份结构做预算，而不是一份。

权重。权重可以直接存放在矩阵单元格中，取代 1 。微妙之处在于非边变成什么： 0 是一个合法的权重，所以值为 0 的单元格是有歧义的。惯例是在最短路径场景中为不存在的边存储 ∞ ，这正是 Floyd-Warshall 开始时的假设；而在流的场景中存储 0 ，因为容量为零的弧和不存在的弧确实是一回事。要有意识地选定一种。在稀疏结构中，权重放在一个与 targets索引方式完全相同的并行数组里，如上面的 CSR 列表所示，这让两者步调一致并保持局部性。把成对数据交错存放也可以，有时还更好；把权重放进一个按边为键的独立哈希表，几乎总是更差。

重数。平行边破坏了邻接矩阵的基本前提，因为一个单元格只能存一个值。常见的补救办法是把重数存为整数计数，这对计数问题有效，却丢掉了每条边自己的数据，比如不同的权重或编号。邻接表则毫无怨言地接受多重边：同一个邻居只是出现不止一次。如果你需要在多重图上保存每条边的属性，就在邻居数组中存储边的编号，并把属性放在一张以这些编号为索引的独立边表中，大多数图数据库正是这么做的。

自环。在 v 处的自环会在对角线上放一个非零值。容易让人栽跟头的约定是：在无向图中，一个自环贡献 2 到顶点 v的度上，因此标准的无向邻接矩阵对单个自环存储 A[v][v] = 2 ，以保持“行和等于度”这一恒等式成立。很多代码却存储 1 ，然后悄悄报告错误的度。在邻接表中，同样的问题变成 v 在它自己的邻居序列中出现一次还是两次，诚实的回答是：你必须做出决定并写进文档，因为两种约定在文献中都存在。

10. 代数表示

一旦图成了矩阵，矩阵运算就有了含义。这不是奇技淫巧，而是一整套图计算风格的基础。

邻接矩阵的幂可以数途径。元素 Ak[u][v] 恰好等于长度为 k 、从 u 到 v的途径数目，这可由矩阵乘法的定义归纳得出。在贯穿示例上：

A^2 =  [ 2  1  1  1  1  0 ]
       [ 1  3  1  0  2  1 ]
       [ 1  1  3  2  0  0 ]
       [ 1  0  2  3  0  0 ]
       [ 1  2  0  0  2  1 ]
       [ 0  1  0  0  1  1 ]

读出 A2[1][4] = 2：从 1 到 4 有两条长度为 2 的途径，即 1→2→4 和 1→3→4。对照图检查一下。对角线 A2[v][v] 是 2、3、3、3、2、1，又是度序列，因为从 v 到自身的长度为 2 的途径，就是走到一个邻居再走回来。再高一次幂， trace(A3) = 6，除以 6 得到一个三角形，穷举验证它就是 {0, 1, 2}。除以 6 是因为每个三角形有三个起点和两个方向。

拉普拉斯矩阵。定义 L = D - A：

L =  [  2 -1 -1  0  0  0 ]
     [ -1  3 -1 -1  0  0 ]
     [ -1 -1  3  0 -1  0 ]
     [  0 -1  0  3 -1 -1 ]
     [  0  0 -1 -1  2  0 ]
     [  0  0  0 -1  0  1 ]

每一行之和为零，所以全 1 向量在核中， L 是奇异的。基尔霍夫矩阵树定理指出，删去任意一行及其对应的列并取行列式，得到的就是图的生成树数目。上面矩阵的六个余子式都等于 11，而枚举全部 C(7,5) = 21 个五边子集并逐一检验是否无环，恰好找到 11 棵生成树。这个定理不是近似，而是恒等式，它把一个看似指数级的计数问题变成一个行列式。

拉普拉斯矩阵的特征值携带更多信息。特征值 0 的重数就是连通分量的个数。第二小的特征值，即 Fiedler 的代数连通度，衡量图有多难被断开，而其特征向量的符号模式给出一个可用的二分划分。这正是谱聚类背后的机制，也是 Chung 的谱图论很大一部分内容的基础。

把图看作半环上的线性代数。这个思想最深刻的版本是：一旦更换算术运算，许多图算法就是矩阵运算。把 (+, ×) 换成 (min, +) ，矩阵乘法就变成最短路径松弛，因此在 min-plus 半环上， An-1 就是所有顶点对最短路径矩阵。把它换成 (OR, AND) ，就变成了可达性。从某个源点出发的广度优先搜索，就是在布尔半环上把稀疏前沿向量反复乘以邻接矩阵。Kepner 和 Gilbert 系统地阐述了这一点，这也正是 GraphBLAS 标准所实现的规范。好处很实际：把算法表达为稀疏矩阵与向量的乘积，就能继承数十年打磨过的并行线性代数，许多 GPU 图计算框架正是这样构建的。

11. 什么时候矩阵更胜一筹

看过第 6 节之后，很容易得出邻接矩阵只是教学工具的结论。事实并非如此，值得准确说明矩阵是正确答案的四种情形。

较小的 n。如果 n 只有几百， n2 也就几万个单元格，内存方面的论据就不复存在。Floyd-Warshall 在矩阵上计算所有顶点对最短路径，时间为 Θ(n3) ，空间为 Θ(n2) ，内层循环只有三行，缓存行为近乎完美；当 n 在几百量级时，它经常胜过在稀疏结构上运行 n 次 Dijkstra，尽管渐近复杂度更差。算法竞赛和运筹学中到处都是这种情形。

真正稠密的图。在前面算出的约 3.1% 密度临界点之上，矩阵不仅更快，而且更小。补图、阈值宽松的相似度图，以及调度问题中的约束图，经常落在这个区间。

位集并行。这是最有力的论据。把矩阵的每一行打包进机器字，邻域上的集合运算就变成按字并行。Arlazarov、Dinic、Kronrod 和 Faradzev 于 1970 年提出的“四个俄罗斯人”方法用于求传递闭包，计算可达性的时间为 O(n3 / log n) ，方法是为比特块预先计算结果；用普通 64 位字实现同样的技巧，几乎不费代码就能在常数因子上获得巨大收益。三角形计数、用分支定界求最大团以及布尔矩阵乘法都依赖于此。稀疏结构根本无法在一条指令里完成 64 次相邻性判断。

能用上快速矩阵乘法。有些图问题可以归约为矩阵乘法并继承其指数。Seidel 算法在无权无向图中计算所有顶点对最短路径，时间为 O(nω log n) ，方法是反复对邻接矩阵求平方，其中 ω 是矩阵乘法指数。Alman 和 Vassilevska Williams 在 2021 年把 ω 降到 2.3729 以下，后续改进又使它略微降低。这些界大多停留在理论层面，因为达到它们的算法常数大到不切实际，但这种归约是真实的，而且只因为图是矩阵才存在。

12. 会变化的图

上面的每种结构都被描述得好像图是固定不变的。许多图并非如此，而更新开销是标准对比表低估了的一个维度。

清晰的情形在两个极端。邻接矩阵的插入和删除都是 O(1)，因为两者都只是一次单元格写入；它的问题从来不是更新速度。边列表追加是 O(1) ，但删除是 O(m)，因为它必须先找到这条边。CSR 两样都做不到：任何结构性修改都要整体重建，用时 Θ(n + m)。

邻接表介于两者之间，稍加用心就有回报。把一个邻居追加到动态数组是 O(1) （摊还）。删除时定位条目需要 O(deg(u)) ，但一旦找到，移除只需 O(1) ，前提是把最后一个元素换到空位上，而不是把后面的元素全部前移。如果在无向图中还需要删除反向副本，就为每个条目存储其孪生条目的位置，这样第二次删除也是 O(1) ，这正是经典的、带配对索引的数组式边表示所做的。

三种模式覆盖了大多数真实需求：

• 批量累积，定期重建。把更新累积在一个小的旁路缓冲区中，查询时同时查 CSR 和缓冲区，当缓冲区超过阈值时重建 CSR。一次重建的开销是 Θ(n + m)，因此把它分摊到 Θ(m) 次更新上，每次更新的开销就是 O(1) ，只要 m 至少为 n，而这几乎涵盖了所有真实的图。大多数分析系统都是这么做的，而且通常就够了。
• 墓碑标记。给被删除的条目打上标记而不是真正移除，并定期压缩。移除条目在找到之后变为 O(1) ，而且其他条目都不移动，所以指向邻居数组的索引仍然有效。但定位条目仍需 O(deg(u)) ，除非你已经持有它的句柄；而且之后每次扫描都得跳过已失效的条目。
• 真正的动态结构。当更新与连通性查询交替进行且两者都必须快速时，数据结构文献自有答案。Link-cut 树和欧拉回路树（Euler tour tree）能以每次操作对数时间维护一个不断变化的森林，任意图上的一般动态连通性就建立在它们之上，每次更新的摊还开销为 O(log2 n) 。它们远比上面的任何结构复杂，只有在批量累积、定期重建的模式经过测量被证明不够用时，才应该动用它们。

一条与硬件相关的警告。在渐近对比表中很快的结构，在实践中可能因为更新导致碎片化而变慢。一个经过一百万次单独插入而增长起来的邻接表，其邻居块会按分配顺序散落在堆上，之后的每次遍历都要在每个顶点上为这种分散付出代价。定期重建为 CSR 往往值得，哪怕只是为了恢复局部性，即使没有任何渐近界发生变化。

13. 隐式图：什么都不存

还有一种表示，也是人们常常忘记其存在的那种：根本不存储图。

所谓隐式图或过程式图，是由一个函数定义的图。你提供的不是数据结构，而是一个后继例程，给定一个顶点，它按需生成该顶点的邻居。任何东西在被访问之前都不会被实体化。

这不是边缘技巧。基本上所有的状态空间搜索都是这样工作的：

• 谜题与游戏的状态空间。魔方构型图大约有 4.3 × 10¹⁹ 个顶点。存储它不是工程投入多少的问题：每个状态一比特就已超过五 EB，而弧按每个状态十八条计算，将超过六 ZB。它的后继函数，即施加十八种面转动之一，只要十几行代码。搜索算法在它上面运行得非常好。
• 规划与模型检验。并发程序的可达状态图是通过执行状态转移生成的。显式状态模型检验器只存储已访问的集合，从不存储边。
• 几何图与网格图。寻路网格有一个显而易见的后继函数：四个或八个偏移量，加上边界和障碍物检查。一个 4096 乘 4096、支持八方向移动的网格，其邻接表有 1.34 亿个条目，而每一个条目都能由一个两行函数精确重现。这一点对网格上的 A*有直接影响。

这些后果值得直白地说出来。空间从图的 Θ(n + m) 降到搜索的 Θ(|visited|) ，正是这一点让该技术变得可行。作为交换，你失去了一切需要看到整个图的能力：你无法统计边数，无法计算度分布，也无法运行任何遍历所有顶点的算法。除非为前驱另写一个函数，否则你也无法廉价地查询前驱；而且每次重新生成邻域都要耗费 CPU，而不是一次内存读取，对于被频繁重访的区域，这可能反而是更昂贵的选择。

隐式表示也是有界内存搜索这一类算法得以成立的前提。迭代加深 A* 只保存当前路径而不保存开放列表，用反复重新生成换取线性空间，而这之所以合理，完全是因为重新生成是可能的。

14. 压缩表示与简洁表示

在网络规模下，连 CSR 都太大了，有两条不同的研究路线在攻克这个问题。

利用结构。 Boldi 和 Vigna 的 WebGraph 框架是这方面的标准参考。它观察到，如果按 URL 给网页排序，同一站点的网页会拥有几乎相同的出链集合，而且它们的目标列表在数值上彼此接近。把每个列表编码为对某个相似的早先列表的引用加上一个小的修正，再用变长编码对剩余目标做差值编码，就能把网页图压缩到每条链接只需几个比特，比原始的 32 位编号好一个数量级。这项技术完全依赖于良好的顶点排序，而这就是普遍的教训：图的压缩主要是一个重新编号的问题。Blandford、Blelloch 和 Kash 针对可分离图（包括平面图和大多数网格）证明了一个互补的结果：基于分隔子的排序可以给出 O(n)比特的表示，同时仍能在常数时间内回答相邻性查询。

简洁数据结构。另一种传统追求这样的表示：其大小逼近信息论下限，同时无需解压就能回答查询。Jacobson 1989 年的工作引入了使之成为可能的 rank 和 select 原语，Munro 和 Raman 又把它推广到树和其他结构。一棵有 n 个节点的有根树只需约 2n 比特，而不是朴素编码所花费的 n 个指针，而且导航仍是常数时间。对图而言一般问题更难，但思路是对的：有 n 个顶点、 m 条边的不同带标号图的数目，给出了大约 m log(n2/m) 比特的下界，一种表示离这个下界有多近，是评判它的一个有意义的标准。

这两条路线都不是默认就该采用的。两者都要付出查询时间，都要付出实现复杂度，只有当图确实装不下时才值得。实用的中间步骤，也是大多数人应当首先尝试的，就是简单地重新给顶点编号，使相邻顶点拥有相近的编号。仅此一项就能可测量地改善普通 CSR 的缓存行为，代价只是一次广度优先遍历。

15. 一套决策流程

把上面的一切浓缩成能在键盘前直接用的东西：

1. 能否由某条规则生成邻居？如果图是状态空间、网格或任何按过程定义的东西，就使用隐式表示，只存储你访问过的部分。
2. 图是稠密的，还是 n 很小？密度高于约 3%，或顶点数少于大约一千时，使用位压缩邻接矩阵。你能得到常数时间的相邻性判断和按字并行的集合运算，在密度临界点之上还能省内存。在临界点之下、 n较小时，矩阵反而是更大的结构，但这根本无关紧要。
3. 你的算法是否只扫描边？ Kruskal、Bellman-Ford 以及任何流式处理都需要边列表。不要建一个你永远不会查询的索引。
4. 加载之后图还会变化吗？如果不会，构建 CSR。如果很少变化，构建带更新缓冲区的 CSR 并定期重建。如果不断变化，使用由动态数组构成的邻接表，并用 swap-and-pop 删除。

然后做两项修正。如果图是有向的并且你需要前驱，就同时构建反向结构，为第二份副本付出代价。如果你的负载中真正占主导的是相邻性判断而不是邻居迭代，先把邻居数组排好序以便二分查找，再考虑哈希集合。

16. 常见错误

• 以为邻接表永远是对的。它是正确的默认选择，但不是万能答案。在一个 500 个顶点的稠密图上，邻接矩阵更小、更简单、更快。
• 对运行在矩阵上的算法声称 O(n + m) 的复杂度。在邻接矩阵上遍历的复杂度是 Θ(n2)。这个界属于表示方式，而不属于伪代码。
• 忘了那个因子 2。无向图在任何邻接结构中都存储 2m 个条目，因为每条边都会出现在两个端点的列表中。把数组大小设为 m 会导致缓冲区溢出，而不只是性能问题。
• 使用 32 位的偏移数组。 CSR 的偏移量索引的是长度为 2m的数组。超过约二十亿条有向弧后，它会悄无声息地溢出并破坏每一次邻居查询。只要 n 低于四十亿，目标数组可以保持 32 位；偏移数组却不行。
• 为不存在的带权边存储零。零是合法的权重。使用 ∞作为哨兵值，或者单独存储边是否存在，或者使用稀疏结构，在其中“不存在”就是没有这个条目。
• 通过排序来构建 CSR。用计数排序构建的开销是 O(n + m)。先对边列表排序的开销是 O(m log m) ，而且没有必要，不过如果你本来就想要有序的邻居数组，这也是个合理的捷径。
• 不存储反向图。在有向 CSR 上查询前驱需要完整扫描目标数组。只要你会做这种查询，就一次性构建转置结构。
• 只凭渐近复杂度选择表示方式。邻接表和 CSR 都是 Θ(n + m)，但由于局部性，CSR 通常要快好几倍。受内存限制的图代码中，常数因子可不是舍入误差。
• 度计数中对自环处理不当。在无向图中，一个自环会使度增加 2。无论你决定邻接结构存储什么，都要让计算度的函数与之保持一致。

17. 术语表

19. 参考文献

上文定义、复杂度界和技术的出处，以及系统阐述这些内容的标准教材，按时间顺序排列。

1. Arlazarov, V. L., Dinic, E. A., Kronrod, M. A. and Faradzev, I. A. (1970). “On economical construction of the transitive closure of a directed graph.” Soviet Mathematics Doklady, 11, 1209–1210.
2. Gustavson, F. G. (1972). “Some basic techniques for solving sparse systems of linear equations.” 载于 Sparse Matrices and Their Applications, Plenum Press, 41–52.
3. Tarjan, R. E. (1972). “Depth-first search and linear graph algorithms.” SIAM Journal on Computing, 1(2), 146–160.
4. Hopcroft, J. and Tarjan, R. E. (1973). “Algorithm 447: efficient algorithms for graph manipulation.” Communications of the ACM, 16(6), 372–378.
5. Aho, A. V., Hopcroft, J. E. and Ullman, J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley.
6. Duff, I. S., Erisman, A. M. and Reid, J. K. (1986). Direct Methods for Sparse Matrices. Oxford University Press.
7. Jacobson, G. (1989). “Space-efficient static trees and graphs.” Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), 549–554.
8. Seidel, R. (1995). “On the all-pairs-shortest-path problem in unweighted undirected graphs.” Journal of Computer and System Sciences, 51(3), 400–403.
9. Chung, F. R. K. (1997). Spectral Graph Theory. CBMS Regional Conference Series in Mathematics 92, American Mathematical Society.
10. Munro, J. I. and Raman, V. (2001). “Succinct representation of balanced parentheses and static trees.” SIAM Journal on Computing, 31(3), 762–776.
11. Blandford, D. K., Blelloch, G. E. and Kash, I. A. (2003). “Compact representations of separable graphs.” Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 679–688.
12. Boldi, P. and Vigna, S. (2004). “The WebGraph framework I: compression techniques.” Proceedings of the 13th International World Wide Web Conference (WWW), 595–602.
13. Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2009). Introduction to Algorithms，第 3 版，第 22 章。MIT Press。
14. Kepner, J. and Gilbert, J., 主编 (2011). Graph Algorithms in the Language of Linear Algebra. Society for Industrial and Applied Mathematics.
15. Diestel, R. (2017). Graph Theory，第 5 版。Springer，Graduate Texts in Mathematics 173。
16. Alman, J. and Vassilevska Williams, V. (2021). “A refined laser method and faster matrix multiplication.” Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 522–539.