图的表示

现实世界里，对象之间的关系往往比对象本身更能决定问题的结构：城市由道路连接，网页通过链接跳转，课程之间有先修次序，任务之间也可能存在依赖。图（$\text{graph}$）把对象抽象为顶点（$\text{vertex}$），把对象之间的关系抽象为边（$\text{edge}$）。但算法不能直接操作纸面上的圆点和连线；要让计算机处理图，还需要回答一个更具体的问题：怎样用数据结构保存“谁与谁相连”？

本节介绍图的两种基本表示——邻接表（$\text{adjacency list}$）与邻接矩阵（$\text{adjacency matrix}$）。它们描述的是同一张图，却把空间分配给不同的对象：邻接表只记录实际存在的边，邻接矩阵则为每一对顶点预留位置。这一差异会直接影响边查询、邻居遍历和后续图算法的成本。

1. 从抽象关系到可计算的数据

一张图记作

其中 $V$ 是顶点集合，$E$ 是边集合；$|V|$ 和 $|E|$ 分别表示顶点数与边数。全文使用下面这张小型交通网络作为例子：

无向边集合为

花括号 $\{u,v\}$ 表示一条无向边（$\text{undirected edge}$）：从 $u$ 到 $v$ 与从 $v$ 到 $u$ 是同一种关系。如果道路改成单行道，就要用有序对 $(u,v)$ 表示有向边（$\text{directed edge}$）；它只说明可以从 $u$ 到达 $v$，并不自动保证可以反向通行。

先在图 1.1 中选一条边，再对照它在图形、邻接表和邻接矩阵中的位置。观察重点不是三幅视图的外观，而是同一条连接怎样被完整保留下来。

三种视图表达的是同一组顶点和边。图形便于人观察，邻接表和邻接矩阵便于算法访问；只要顶点编号与边的对应关系没有丢失，表示方式的变化就不会改变图本身。

2. 邻接表：只记录真实存在的连接

邻接表为每个顶点维护一组邻居。记 $\operatorname{Adj}[u]$ 为顶点 $u$ 的邻接表，其中保存所有满足 $(u,v)\in E$ 的顶点 $v$。上面的交通网络可以写成：

A: B, C
B: A, C, D
C: A, B, E
D: B, E
E: C, D

例如，从 $B$ 对应的一行可以直接读出三个邻居 $A、C、D$。邻接表没有为 $B$ 与 $E$ 预留空位置，因为这条边并不存在。

这里的“表”描述的是一种组织方式，并不要求实现时使用传统链表。实际程序可以采用数组、动态数组、链表、集合，或从顶点编号映射到邻居数组的哈希表（$\text{hash table}$）。具体实现会影响常数开销（$\text{constant overhead}$）和某些操作的成本，但不会改变邻接表的核心思想：以顶点为入口，只记录实际存在的邻接关系。

2.1 有向边与无向边要记录几次

对有向边 $(u,v)$，只需在 $\operatorname{Adj}[u]$ 中记录 $v$。因此，所有邻接表的长度之和等于边数：

对无向边 $\{u,v\}$，既要在 $\operatorname{Adj}[u]$ 中记录 $v$，也要在 $\operatorname{Adj}[v]$ 中记录 $u$。同一条边会出现两次，所以

无论图是否有向，为每个顶点保留一个邻接表入口需要 $\Theta(|V|)$ 空间，保存全部邻接项需要 $\Theta(|E|)$ 空间。因此，邻接表的总空间复杂度为

2.2 遍历邻居为什么是邻接表的强项

当算法处理顶点 $u$ 并需要访问从 $u$ 能直接到达的所有顶点时，只需顺序扫描 $\operatorname{Adj}[u]$。在有向图中，这一过程与 $u$ 的出度（$\text{out-degree}$，记作 $\deg^+(u)$）成正比，需要 $\Theta(\deg^+(u))$ 时间；在无向图中则需要 $\Theta(\deg(u))$ 时间，其中 $\deg(u)$ 是 $u$ 的度（$\text{degree}$）。广度优先搜索（$\text{Breadth-First Search}$，BFS）和深度优先搜索（$\text{Depth-First Search}$，DFS）经常采用邻接表，正是因为它们会反复枚举当前顶点的邻居。

如果要判断指定边 $(u,v)$ 是否存在，使用数组或链表保存邻居时，算法必须在 $\operatorname{Adj}[u]$ 中寻找 $v$，最坏需要 $\Theta(|\operatorname{Adj}[u]|)$ 时间。改用哈希集合（$\text{hash set}$）可以加快查询，但会占用更多空间，也可能改变邻居的遍历顺序。表示方式之外，邻接项采用什么数据结构仍然是一项需要明确的取舍。

图 2.1 把“添加一条边”拆成具体的存储动作。切换有向图与无向图，比较一次操作究竟会修改一个还是两个邻接表入口。

有向边只从起点指向终点，因此写入一次；无向边需要从两个端点都能找到对方，因此写入两次。这个差别也解释了上一小节中 $|E|$ 与 $2|E|$ 的计数结果。

2.3 一种现代代码表示

下面的 TypeScript 类型把每个邻接项写成一个对象：$to$ 保存终点编号，$weight$ 保存可选边权。顶点编号为 $0,1,\ldots,|V|-1$ 时，外层数组的下标就能直接代表顶点。

type Edge = {
  to: number;       // 邻接点编号
  weight?: number;  // 可选边权；无权图可以省略
};

type AdjacencyList = Edge[][];

const graph: AdjacencyList = [
  [{ to: 1 }, { to: 2 }],
  [{ to: 0 }, { to: 2 }, { to: 3 }],
  [{ to: 0 }, { to: 1 }, { to: 4 }],
  [{ to: 1 }, { to: 4 }],
  [{ to: 2 }, { to: 3 }],
];

这段代码仍然体现“顶点作为入口、邻接项只记录现有边”的结构。如果顶点使用城市名、网页 URL 等非整数标识，可以先建立“外部标识到连续整数”的映射，既保留业务含义，也让底层数组保持紧凑。

3. 邻接矩阵：为每一对顶点预留位置

邻接表从顶点出发寻找真实存在的边；如果算法更关心“任意两个顶点之间是否有边”，可以反过来为每一对顶点预留一个位置。固定顶点顺序后，建立 $|V|\times|V|$ 的矩阵 $A=(a_{ij})$。对只记录边是否存在的无权图（$\text{unweighted graph}$），可以定义

交通网络按 $A,B,C,D,E$ 排列后，对应矩阵为

图 3.1 允许选择一对顶点。操作前先预测对应的行、列和单元格，再检查该位置的值是否与边的存在性一致。

矩阵中的每个单元格都对应一对顶点，即使图中没有相应的边，这个位置仍然存在。因此，邻接矩阵始终需要 $\Theta(|V|^2)$ 空间，而这一占用不随实际边数改变。它换来的好处是直接访问 $A[u][v]$，从而在 $\Theta(1)$ 时间内判断 $(u,v)$ 是否存在。邻接矩阵用固定的平方级空间换取了直接的边查询。

3.1 无向图的矩阵为什么对称

在无向图中，$\{u,v\}$ 同时意味着“$u$ 与 $v$ 相邻”和“$v$ 与 $u$ 相邻”，所以

从整体上看，邻接矩阵满足

图 3.2 将一侧单元格的变化映射到主对角线另一侧。观察任意一条无向边对应的两个 $1$，它们到主对角线的距离始终相同。

因此，无向图的邻接矩阵关于主对角线对称。理论上只保存主对角线及其一侧就能避免重复，但这种压缩会增加索引计算；当图不大、实现清晰度更重要时，完整矩阵通常更容易使用。

对不含自环和平行边的简单图（$\text{simple graph}$），主对角线元素均为 $0$。如果存在自环（$\text{self-loop}$）$(u,u)$，那么 $a_{uu}=1$。因此，主对角线也记录了各顶点是否连接到自身。

3.2 有向图与转置图

有向图的邻接矩阵通常不对称，因为 $(u,v)$ 存在并不代表 $(v,u)$ 也存在。把所有边的方向反转，可以得到转置图（$\text{transpose graph}$）

图 3.3 展示一条边反向后，矩阵中的标记怎样从 $A[u][v]$ 移到 $A[v][u]$。把这一变化推广到全部边，就能看到整张矩阵发生转置。

在矩阵表示中，转置图的邻接矩阵就是 $A^{\mathsf T}$。在邻接表表示中，则要扫描全部顶点及其出边，把每条 $(u,v)$ 写入新图的 $\operatorname{Adj}^{\mathsf T}[v]$，总计需要 $\Theta(|V|+|E|)$ 时间。转置图不仅是一种形式变换，后续的强连通分量算法还会直接使用它。

4. 边除了存在，还能记录什么

许多图问题不仅关心顶点是否相连，还要记录距离、费用、容量或时间。为每条边附上数值的图称为带权图（$\text{weighted graph}$），其边权函数可以写作

这里的 $\mathbb{R}$ 表示实数集，即每条边都对应一个实数权值。在邻接表中，可以把邻接项从顶点 $v$ 扩展成 $(v,w(u,v))$；在邻接矩阵中，则可以令 $A[u][v]=w(u,v)$。

这里有一个容易被忽略的问题：不存在的边应该用什么值表示？如果合法边权可能为 $0$，就不能再用 $0$ 表示“没有边”。实现时可以使用 null、undefined、单独的布尔矩阵，或由具体算法约定的 $+\infty$。这类专门表示特殊状态的值称为哨兵值（$\text{sentinel value}$）；它必须位于合法数据范围之外，否则程序就无法区分真实权重与“边不存在”。

4.1 图结构与算法属性为什么要分开

邻接表和邻接矩阵描述的是图的连接结构——哪些顶点由哪些边连接。搜索算法还会另外维护颜色、距离、前驱和时间戳等算法属性（$\text{algorithm attributes}$）。二者有关联，却不应混为一体。

例如，BFS 的 $u.d$ 和 $u.\pi$（即下一篇定义的距离与前驱字段）可以保存在与顶点编号平行的数组中，也可以作为顶点对象的字段；边权既可以跟随邻接项保存，也可以放在单独的映射中。

改变颜色或距离不会改变图的边集。重新运行算法时应重置算法属性，却不必重建图结构。具体组织方式可以根据访问频率、内存局部性（$\text{memory locality}$）以及同一张图是否会被多个算法复用来选择。

5. 稀疏与稠密怎样影响空间取舍

若不允许自环，含 $n=|V|$ 个顶点的简单有向图最多有 $n(n-1)$ 条边，简单无向图最多有 $n(n-1)/2$ 条边；二者的边数上限都为 $\Theta(n^2)$。当实际边数远小于这个上限时，称为稀疏图（$\text{sparse graph}$）；当大量顶点对之间都有边时，则称为稠密图（$\text{dense graph}$）。

假设有 $10{,}000$ 个顶点和 $30{,}000$ 条有向边。邻接表需要保存 $30{,}000$ 个邻接项，此外为 $10{,}000$ 个顶点保留入口；完整邻接矩阵则需要 $100{,}000{,}000$ 个单元格。此时，为不存在的边预留位置会造成明显浪费。反过来，如果图很小、接近任意两个不同顶点之间都有边的完全图（$\text{complete graph}$），并且程序频繁查询任意两点之间是否有边，邻接矩阵的直接索引可能更合适。

实验 5.1 把边逐步加入同一组顶点。操作前先预测：随着边数增加，邻接表实际保存的邻接项会怎样变化？邻接矩阵的单元格总数又会不会变化？

实验表明，邻接表的空间随实际边数增长，邻接矩阵的空间则主要由顶点数决定。因此，“邻接表一定优于邻接矩阵”并不成立；真正需要比较的是图的密度、算法的高频操作和实现所需的访问模式。

6. 常见操作的成本如何比较

下表的结论基于两个假设：邻接表使用数组或链表保存邻居，矩阵支持按下标随机访问。若换成哈希集合、有序集合或压缩矩阵，具体结果会随实现改变。

表 6.1 中，$\Theta(\cdot)$ 表示与括号内的量同阶，$O(\cdot)$ 表示“不超过该阶”的宽松上界；$\deg^+(u)$ 是有向图中 $u$ 的出度，在无向图中可换成 $\deg(u)$。数组尾部添加邻接项通常称为均摊复杂度（$\text{amortized complexity}$）$O(1)$，因为偶尔发生的扩容成本会被分摊到多次插入中。

对照表 6.1 可以看到，两种表示没有统一胜负：邻接表更擅长只访问真实存在的边，邻接矩阵更擅长直接定位任意顶点对。选型时应先确认高频操作，再比较相应的时间与空间成本。

7. 表示方式怎样影响后续算法

图的表示不是与算法无关的预处理细节。BFS 从队列中取出顶点后要枚举它的邻居，DFS 也会沿邻接关系继续深入。对稀疏图，如果使用邻接矩阵，这些算法为了找到少量真实边，仍要逐行检查大量值为 $0$ 的单元格；使用邻接表时，完整遍历只需 $\Theta(|V|+|E|)$ 时间。

另一方面，有些算法本来就要对大量顶点对进行计算，或核心操作就是矩阵更新。此时，邻接矩阵不仅更直接，还可能与算法的数学形式一致。选择表示方式时，应以后续算法最常执行的操作为依据，不能只比较初始化是否方便。

在进入具体算法前，可以按下面五步缩小选择范围：

这些判断最终会落实为算法运行时的局部访问。图 7.1 允许选择当前顶点；操作时观察它的邻居、度和关联边如何同步变化，并留意顶点在画布上的位置是否影响邻接关系。

顶点的位置只帮助读者辨认图形，并不是图结构的一部分。算法真正读取的是当前顶点对应的邻接信息；这也是同一张图更换布局后，BFS 或 DFS 的可达性结论仍然不变的原因。

最后用实验 7.1 综合检验两种表示。添加或删除一条边之前，先预测邻接表中哪些条目会变化、邻接矩阵中哪些单元格会翻转，再操作并核对两种表示是否仍描述同一张图。

只要两种表示同步更新，它们给出的邻接关系就应完全一致；变化的是存储布局和操作成本，而不是图的数学含义。

8. 小结

邻接表与邻接矩阵是同一张图的两种存储视角。邻接表只记录实际存在的连接，空间为 $\Theta(|V|+|E|)$，尤其适合稀疏图和邻居遍历；邻接矩阵为每一对顶点保留单元格，空间为 $\Theta(|V|^2)$，换来 $\Theta(1)$ 的直接边查询。

有向、无向和带权只会改变边怎样写入这两种结构，并不会改变它们的基本取舍。选择表示方式时，应同时考虑图的密度、边上的附加信息以及后续算法的高频操作，而不是把其中一种视为默认答案。

下一篇将从这些存储结构出发学习广度优先搜索。届时，$\operatorname{Adj}[u]$ 不再只是一个定义：算法会反复读取它，并从源点开始一层一层扩展到所有可达顶点。