图的表示

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

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

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

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

删除无向边 $\{u,v\}$ 必须同时从 $u$ 的表中删去 $v$、从 $v$ 的表中删去 $u$。若两个无序数组没有互指位置索引，就要分别寻找两个记录，因此主表的界是 $O(1+\mathrm{deg}(u)+\mathrm{deg}(v))$。只删除一端会使表示不再对称，让从不同方向开始的搜索得到互相矛盾的连通信息。

例如邻接表为 $a:[b,c],b:[a],c:[a]$，删除 $\{a,b\}$ 后应变成 $a:[c],b:[],c:[a]$，顶点 $b$ 仍须保留。若允许无序排列，找到记录后可用末项覆盖再缩短数组；若要保持邻居顺序，则还须移位。满足前述条件的哈希集合提供期望常数查找时间，有序集合提供对数时间；允许重复边时，还要说明删除一条、全部还是按边标识删除。

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

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

平面细分若还需绕面、跨边和枚举顶点周围的面，可使用双向连接边表公理库双向连接边表（DCEL）Doubly-connected edge list · DCEL用成对半边、面边界环与顶点关联，把平面细分的局部导航和修改组织成可检查的链接不变量。保存半边、环绕次序与面关联；普通邻接表只记录连边，不能自动恢复这些嵌入信息。

静态稀疏图还可把所有邻接表首尾相接存入一个数组，用长度为 $n+1$ 的偏移表记录每个顶点的区间。顶点 $u$ 的邻居就是半开区间 $[\mathrm{offset}[u],\mathrm{offset}[u+1])$；孤立点对应空区间。这种压缩稀疏行表示保留线性遍历成本，却使中间插边可能需要移动后续记录，说明布局更紧凑不等于动态更新更便宜。