图的表示 | Codeboy's Blog

形式陈述

本页主表固定基础有限简单无向图 $G=(V,E)$ ，记 $n=|V|$ 、 $m=|E|$ 。邻接矩阵以 $n\times n$ 的数组 $A$ 表示边， $A[u,v]$ 是 Boolean 值且满足 $A[u,v]=A[v,u]$ 。邻接表为每个顶点 $u$ 存储邻居容器 $\operatorname{Adj}[u]$ ；每条非自环边 $\{u,v\}$ 分别在 $u$ 与 $v$ 的表中出现一次，因此所有表项总数为 $2m$ 。边集表示则直接存储无序端点对 $\{u,v\}$ 。

下表采用这些操作模型：邻接矩阵直接寻址；邻接表的邻居容器为无序序列，且“加边”一栏假设调用者已知该边不存在，或表示本身允许重复记录。若简单图接口必须先防止重边，需先付出 $O(\deg(u))$ 的查边成本。若改成哈希集合，查边可得期望 $O(1)$ ，但空间和常数因子随之改变。

表示	空间	查询边 $uv$	遍历 $u$ 的邻居	加边	删边
邻接矩阵	$\Theta(n^2)$	$O(1)$	$\Theta(n)$	$O(1)$	$O(1)$
邻接表（无序序列）	$\Theta(n+m)$	$O(\deg(u))$	$\Theta(\deg(u))$	摊还 $O(1)$	$O(\deg(u))$
边集（无索引序列）	$\Theta(m)$	$O(m)$	$O(m)$	摊还 $O(1)$	$O(m)$

变体

有向图的邻接表通常存出弧，遍历入弧需另建反向表；邻接矩阵不再要求对称。带权图把 Boolean 或邻居编号扩展为含权记录。多重图必须让同一端点对对应多条独立边，或在只关心重数时显式存储 multiplicity。它们改变记录与操作语义，不能直接沿用主表的 $2m$ 计数和 Boolean 单元解释。

直觉

表示不是算法写完后的存储细节，而是算法能以多大代价看到图。广度优先搜索需要反复枚举当前顶点的邻居：邻接表只触碰实际存在的边，得到 $O(n+m)$ ；矩阵每次都扫描整行，哪怕多数位置为零，也会累积到 $O(n^2)$ 。反过来，若算法频繁询问任意一对顶点是否相邻，矩阵的一次寻址可能比线性扫描邻居表更合适。

因此“矩阵更快”或“邻接表更省空间”都缺少条件。图的稀疏程度、是否动态修改、是否要遍历入边、是否允许平行边，以及邻居容器本身是数组、哈希集还是有序树，共同决定真实成本。

例子与边界

对道路网络这类稀疏图， $m$ 通常与 $n$ 同阶。用邻接表运行 BFS时，每个顶点入队至多一次，每条无向边的两个表项各检查一次，总工作量为 $\Theta(n+m)$ ；改用矩阵，即使某个路口只有三条路，也要扫描长度为 $n$ 的整行，最终为 $\Theta(n^2)$ 。在顶点很少而边接近完全的图上，两种空间量级趋近，矩阵的直接查边反而可能更简单。

多重图揭示 Boolean 矩阵的边界：两点间两条不同容量的边若都只写成 true，重数和权值都会丢失。可以让矩阵单元存边列表或重数，但此时操作语义与空间分析必须重新说明。自环也要求明确约定：邻接矩阵只占对角线上一个单元，而无向邻接表是存一个表项还是按度数贡献二存两个表项，不同实现皆可，计数公式必须与约定一致。

删除边的成本同样不能脱离容器来写。无序数组需要先找到目标，哈希集合通常提供期望常数时间，有序集合提供对数时间；若允许重复边，还要说明删除一条、全部还是按边标识删除。

推论与应用

DFS、BFS 与强连通分量算法的 $O(V+E)$ 界隐含了能按出边总量遍历的表示。Prim 算法在稠密图上可直接用矩阵做 $O(V^2)$ 实现，在稀疏图上则常把邻接表与优先队列组合。邻接矩阵还便于使用矩阵乘法、位集合和 GPU 并行操作，邻接表则自然支持逐边松弛。

从文件或网络读入的边集适合交换与批处理，却通常不是查询阶段的最终索引。常见流程是先接收边记录，再依据下游操作建立恰好需要的表示；若同时维护矩阵和邻接表，就必须承担二者同步更新的不变量。

参考资料

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，§20.1, representations of graphs。
Erik D. Demaine and Srini Devadas, MIT 6.006 Lecture 13: Breadth-First Search, graph representations and adjacency lists, accessed 2026.

形式陈述 ​

变体 ​

反向链接

形式陈述

变体