数据结构与算法 / 系统课时
邻接表和邻接矩阵怎么选
邻接表和邻接矩阵怎么选
同一张图可以用不同数据结构保存,选择不当会直接影响内存占用和关键操作复杂度。本篇从图的稠密程度、是否频繁查边以及后续算法需要什么出发,建立邻接表与邻接矩阵的实用选择标准。
学习目标
- 理解邻接表和邻接矩阵各自保存了什么信息。
- 能根据顶点数、边数和主要操作估算空间与访问复杂度。
- 能在稀疏图、稠密图和频繁查边场景中做出合适选择。
先看两个决定性问题
选择表示方式时,先确定图有多“密”,再确定程序最常做什么操作。设顶点数为 ,边数为 。无向简单图最多约有 条边,有向简单图最多约有 条边。
如果实际的 远小于 ,通常称为稀疏图;如果大量顶点彼此相连,则更接近稠密图。第二个问题是:程序主要遍历某个顶点的邻居,还是经常直接查询“顶点 到 是否有边”。
这两个问题往往已经能决定大部分场景。
邻接表更适合稀疏图
邻接表为每个顶点保存一个邻居集合,只记录真实存在的边。典型空间复杂度是 ,因此边很少时不会为“不存在的关系”浪费大量空间。
遍历顶点 的所有邻居时,只需要访问与 相连的边,代价与 的度数成正比。BFS、DFS、拓扑排序以及大多数基于邻居扩展的图算法通常更适合这种表示。
它的弱点是“查某一条特定边”不一定快。如果邻居集合使用普通数组或链表,判断 u -> v 是否存在,最坏需要扫描 的全部邻居。若业务既希望节省空间又需要频繁查边,可以为每个顶点使用哈希集合,但会增加常数开销和实现成本。
邻接矩阵更适合频繁查边
邻接矩阵使用一个 的二维结构,第 行第 列直接表示两点之间是否有边,或者保存对应权重。它的空间复杂度是 ,与实际边数无关。
最大优势是查边稳定为 。如果算法需要大量回答“这两个点是否相连”,或者图本身非常稠密,矩阵的直接访问通常更简单。某些以矩阵为核心的算法也天然适合这种表示。
代价同样明显:当 很大而 很小时,大部分单元格都在表示“没有边”。例如 时, 级别的存储通常已经不可接受,即使实际只有几十万条边。
用操作模式做最后选择
可以把选择压缩为下面的判断:
| 需求 | 邻接表 | 邻接矩阵 |
|---|---|---|
| 稀疏图 | 更合适,空间约 | 通常浪费空间 |
| 稠密图 | 可用 | 常更直接 |
| 遍历某点所有邻居 | 高效 | 需要扫描整行 |
| 频繁判断两点是否有边 | 取决于邻居容器 | |
| 顶点数很大 | 通常更可控 | 容易出现 内存压力 |
不要只因为“矩阵查边快”就默认使用矩阵,也不要只因为“邻接表省空间”就忽略操作模式。表示方式最终服务于后续算法。
还要注意的实现边界
有权图中,矩阵需要一个明确值表示“没有边”,这个值必须和合法权重区分。若权重可能为 0,就不能简单把 0 同时当作“无边”。
无向图使用邻接表时,一条无向边通常要在两个顶点的邻居集合中各记录一次,因此实现层面会存两条邻接记录,但图论里的边数仍然按一条边计算。分析复杂度时要保持这个口径一致。
实际工程中,默认从邻接表开始通常更稳妥;当图较稠密、顶点规模可控,或核心操作是大量 查边时,再考虑邻接矩阵。选择依据始终是数据规模与操作模式的组合,而不是数据结构本身的“优劣”。