邻接表是一种用于表示图论中的图的数据结构,它为每个顶点关联一组邻居或关联边。它只存储实际存在的连接,而不会为每一种可能的顶点对单独预留位置。因此,它特别适用于稀疏图,即边数相对于可能的连接数较少的图。虽然名称中带有“表”,邻接表并不一定要使用链表:数组、可调整大小的数组、哈希表及其他容器都可以用来存储邻居。
定义与结构
设图为 ,其中 是顶点集, 是边集。对于有向图,顶点 的出边邻接集合表示为
这一集合记法描述的是简单图。在具体实现中,也可以存储边记录序列,从而允许端点重复,并保存边标识符及其他属性。
邻接表表示通常分为两层:
- 外层容器,用于定位每个顶点的邻接集合。
- 内层容器,用于存储该顶点的邻居或边记录。
如果顶点采用连续编号,外层容器可以使用数组(数据结构)。如果顶点以名称或其他键标识,则可以用哈希表将标识符映射到相应的集合。没有邻居的顶点也必须得到表示,例如使用空集合,或在单独的顶点登记表中为其保留条目。
示例
考虑一个无向图,其顶点为 ,边为 、 和 :
A: B, C
B: A, D
C: A
D: B
E:
每条边都出现在两个端点各自的集合中。孤立顶点 对应的集合为空。
对于相应的有向边 、 和 ,出边邻接表示为:
A: B, C
B: D
C:
D:
E:
邻居的排列顺序通常没有数学意义,但可能影响遍历顺序以及结果的可复现性。
图的变体与边属性
有向图与无向图
在没有自环的无向图中,每条边对应两个邻接条目。因此,顶点的度就是其邻接集合的长度。
在有向图中,出边表记录从某个顶点出发的边。它的长度给出该顶点的出度,而非入度。若要高效访问入边,就需要单独的入边邻接结构或其他索引。如果没有这类结构,查找某个顶点的所有前驱可能需要扫描整个图。
加权图
对于加权图,每个条目可以包含一个邻居及相应的权重:
A: (B, 7), (C, 2)
B: (D, 5)
更一般的边记录还可以包含标识符、标签、容量、时间戳,或指向单独存储的属性的引用。将属性保存在共享的边对象中,可以避免在无向边的两个端点都引用该边时重复存储属性。
平行边与自环
多重图允许同一对端点之间存在多条边。邻接序列可以用独立的记录表示这些边;而仅存储邻居的集合会将它们合并,除非显式保存边的重数或边集合。
自环的处理约定需要格外注意。在无向图中,一个自环对所在顶点的数学意义上的度贡献为二。具体表示时,可以将自环存储两次,以保持度与表长之间的对应关系;也可以只存储一次,并在计算度时单独处理。
空间与操作开销
记 ,。通常假设每个顶点条目和每条边记录占用的空间均有固定上界,在此假设下,邻接表使用的空间为
有向图的出边表示存储 个边条目;常规的无向图表示则存储约 个。空间复杂度中的顶点项不可忽略,因为孤立顶点也需要得到表示。
各项操作的时间复杂度取决于所选容器。对于未排序的邻接序列,假设访问外层顶点条目所需的时间为常数,则有:
| 操作 | 典型开销 |
|---|---|
| 枚举 的所有邻居 | |
| 判断 是否与 相邻 | |
| 在链表头部插入一个条目 | |
| 在可调整大小的数组末尾追加一个条目 | 均摊 |
| 按端点查找并删除一个条目 | |
| 枚举所有顶点和边 |
对于有向图的出边表,这些开销中的 指出度。
上述界限需要附加若干说明:
- 常数时间插入以无需检查是否已存在重复项为前提。
- 删除无向边通常需要同时更新两个端点的集合。
- 删除已知条目可能比定位该条目更快,具体取决于容器以及可用的引用。
- 删除顶点时,还必须删除与其关联的边。如果只有出边表,定位该顶点的入边可能需要进行完整扫描。
- 大小可变的边属性和顶点标识符会带来额外的存储需求,不包含在结构本身的 界限内。
因此,“邻接表”规定的是一种表示模式,而不是一套适用于所有实现的操作开销。
实现选择
链表与可调整大小的数组
链表支持在头部进行常数时间插入;如果有合适的引用,也可以支持高效删除。其缺点包括指针开销、内存分配成本,以及节点在内存中分散存放时较差的局部性。
动态数组将邻居连续存储。它通常能提供紧凑的存储和高效的顺序迭代,并受益于CPU 缓存。在末尾追加元素的均摊开销为常数,但删除元素可能需要移动其他元素。如果不必保持顺序,可以用最后一个元素替换待删除的已知元素,再缩小数组。
有序集合与哈希集合
有序邻接数组允许通过二分查找在 时间内查找端点,但更新时为了维持顺序,可能需要线性时间的操作。
在合适的哈希假设下,基于哈希的邻居集合可以提供期望常数时间的成员查询和更新操作。它会引入额外的内存开销,迭代时的局部性可能较差,而且如果每个邻居只存储一次,就无法直接保留平行边。
压缩稀疏行存储
压缩稀疏行格式,简称 CSR,将邻接数据紧凑地存入一个偏移量数组和一个连续的邻居数组中。对于编号为 的顶点,顶点 的邻居占据以下左闭右开区间:
偏移量数组包含 个条目。加权图的表示可以使用一个与邻居数组对应的权重数组来存储权重。
CSR 减少了逐顶点分配内存的开销,并支持高效的顺序处理。它很适合静态图,但图结构发生变化时,可能需要移动数据或重建表示。
在图算法中的应用
邻接表使算法能够直接检查实际存在的边,而不必检查所有可能的顶点对。
假设辅助记录操作均可在常数时间内完成,广度优先搜索和深度优先搜索遍历以邻接表表示的整个图时,运行时间为 。每个顶点的处理次数和每个邻接条目的检查次数都有常数上界。从一个顶点出发的遍历只会访问从该顶点可达的部分,除非再发起其他搜索。
对于最短路径问题,迪ijkstra算法通常将加权邻接表与优先队列配合使用。在边权非负的情况下,采用二叉堆的标准实现,其运行时间为 。
邻接表还用于拓扑排序、连通分量检测、生成树算法以及网页排名算法。它们广泛出现在道路网络、依赖关系图、社交网络和程序分析结构中。
与其他表示方式的比较
邻接矩阵为每个有序顶点对预留一个位置。因此,常规矩阵需要 个条目,支持常数时间的边查询,而枚举某个顶点的邻居通常需要扫描长度为 的一整行。
相比之下,邻接表使用的空间与顶点数和边数之和成正比,枚举邻居所需的时间则与邻居数量成正比。对于稀疏图以及以遍历为主的工作负载,邻接表通常很有吸引力。对于稠密图,矩阵凭借简单的索引、可预测的内存访问以及高效的位压缩表示,可能同样具有竞争力,甚至更为合适。
边列表将所有边存储在由端点对或边记录组成的单一集合中。它便于处理或排序全部边,但如果没有额外建立索引,查找某个顶点的邻居就需要扫描整个集合。
实际选择不仅取决于图的稠密程度,还取决于更新频率、成员查询频率、边属性、内存开销和访问模式。即使一个图在数学意义上是稀疏的,如果每个邻接条目都带有多个指针或单独分配的对象,仍可能产生可观的内存开销。