数据结构与算法 / 系统课时

邻接表和邻接矩阵怎么选

邻接表和邻接矩阵怎么选

同一张图可以用不同数据结构保存,选择不当会直接影响内存占用和关键操作复杂度。本篇从图的稠密程度、是否频繁查边以及后续算法需要什么出发,建立邻接表与邻接矩阵的实用选择标准。

学习目标

  • 理解邻接表和邻接矩阵各自保存了什么信息。
  • 能根据顶点数、边数和主要操作估算空间与访问复杂度。
  • 能在稀疏图、稠密图和频繁查边场景中做出合适选择。

先看两个决定性问题

选择表示方式时,先确定图有多“密”,再确定程序最常做什么操作。设顶点数为 VV,边数为 EE。无向简单图最多约有 V(V−1)/2V(V-1)/2 条边,有向简单图最多约有 V(V−1)V(V-1) 条边。

如果实际的 EE 远小于 V2V^2,通常称为稀疏图;如果大量顶点彼此相连,则更接近稠密图。第二个问题是:程序主要遍历某个顶点的邻居,还是经常直接查询“顶点 uu 到 vv 是否有边”。

这两个问题往往已经能决定大部分场景。

邻接表更适合稀疏图

邻接表为每个顶点保存一个邻居集合,只记录真实存在的边。典型空间复杂度是 O(V+E)O(V+E),因此边很少时不会为“不存在的关系”浪费大量空间。

遍历顶点 uu 的所有邻居时,只需要访问与 uu 相连的边,代价与 uu 的度数成正比。BFS、DFS、拓扑排序以及大多数基于邻居扩展的图算法通常更适合这种表示。

它的弱点是“查某一条特定边”不一定快。如果邻居集合使用普通数组或链表,判断 u -> v 是否存在,最坏需要扫描 uu 的全部邻居。若业务既希望节省空间又需要频繁查边,可以为每个顶点使用哈希集合,但会增加常数开销和实现成本。

邻接矩阵更适合频繁查边

邻接矩阵使用一个 V×VV \times V 的二维结构,第 uu 行第 vv 列直接表示两点之间是否有边,或者保存对应权重。它的空间复杂度是 O(V2)O(V^2),与实际边数无关。

最大优势是查边稳定为 O(1)O(1)。如果算法需要大量回答“这两个点是否相连”,或者图本身非常稠密,矩阵的直接访问通常更简单。某些以矩阵为核心的算法也天然适合这种表示。

代价同样明显:当 VV 很大而 EE 很小时,大部分单元格都在表示“没有边”。例如 V=100000V=100000 时,V2V^2 级别的存储通常已经不可接受,即使实际只有几十万条边。

用操作模式做最后选择

可以把选择压缩为下面的判断:

需求 邻接表 邻接矩阵
稀疏图 更合适,空间约 O(V+E)O(V+E) 通常浪费空间
稠密图 可用 常更直接
遍历某点所有邻居 高效 需要扫描整行
频繁判断两点是否有边 取决于邻居容器 O(1)O(1)
顶点数很大 通常更可控 容易出现 O(V2)O(V^2) 内存压力

不要只因为“矩阵查边快”就默认使用矩阵,也不要只因为“邻接表省空间”就忽略操作模式。表示方式最终服务于后续算法。

还要注意的实现边界

有权图中,矩阵需要一个明确值表示“没有边”,这个值必须和合法权重区分。若权重可能为 0,就不能简单把 0 同时当作“无边”。

无向图使用邻接表时,一条无向边通常要在两个顶点的邻居集合中各记录一次,因此实现层面会存两条邻接记录,但图论里的边数仍然按一条边计算。分析复杂度时要保持这个口径一致。

实际工程中,默认从邻接表开始通常更稳妥;当图较稠密、顶点规模可控,或核心操作是大量 O(1)O(1) 查边时,再考虑邻接矩阵。选择依据始终是数据规模与操作模式的组合,而不是数据结构本身的“优劣”。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

邻接表和邻接矩阵怎么选

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通