图的表示

形式陈述 ​

设图 $G=(V,E)$，$n=|V|$、$m=|E|$。邻接矩阵以 $n\times n$ 的数组公理库数组Array以连续整数下标支持随机访问的有限序列结构。 $A$ 表示边，简单图中 $A[u,v]$ 是 Boolean 值；无向图满足 $A[u,v]=A[v,u]$。邻接表为每个顶点 $u$ 存储邻居容器 $\mathrm{Adj}[u]$；无向非自环边 $\{u,v\}$ 通常分别在 $u$ 与 $v$ 的表中出现一次，因此所有表项总数为 $2m$。边集表示则直接存储边记录 $(u,v)$ 或 $(u,v,w)$。

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

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

有向图中邻接表通常存出边，遍历入边需另建反向表；带权图把 Boolean 或邻居编号扩展为权值记录；多重图必须允许同一端点对对应多条边或存储重数。

直觉 ​

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

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

例子与边界 ​

对道路网络这类稀疏图，$m$ 通常与 $n$ 同阶。用邻接表运行 BFS公理库广度优先搜索Breadth-first search · BFS按无权距离分层访问可达顶点的图遍历算法。时，每个顶点入队至多一次，每条无向边的两个表项各检查一次，总工作量为 $\mathrm{\Theta }(n+m)$；改用矩阵，即使某个路口只有三条路，也要扫描长度为 $n$ 的整行，最终为 $\mathrm{\Theta }(n^2)$。在顶点很少而边接近完全的图上，两种空间量级趋近，矩阵的直接查边反而可能更简单。

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

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

推论与应用 ​

DFS公理库深度优先搜索Depth-first search · DFS沿未访问边尽可能深入后回溯的图遍历算法。、BFS 与强连通分量算法的 $O(V+E)$ 界隐含了能按出边总量遍历的表示。Prim 算法公理库Prim 算法Prim's algorithm从一个顶点开始反复加入跨越当前割的最轻边的最小生成树算法。在稠密图上可直接用矩阵做 $O(V^2)$ 实现，在稀疏图上则常把邻接表与优先队列公理库优先队列Priority queue · Priority queue ADT按键的优先次序反复访问并移除当前最小元素的抽象数据类型。组合。邻接矩阵还便于使用矩阵乘法、位集合和 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 Justin Solomon, MIT 6.006, Graphs, lecture notes，adjacency arrays, adjacency lists, and operation costs。