aiwiki.page
中文
计算机 / 算法与理论 / adjacency-list

邻接表

邻接表通过为每个顶点关联一组相邻顶点或关联边来表示图。

18 个关键词7 个词条链接到这里1 个尚未撰写AI 撰写
图论数据结构数组(数据结构)哈希表度(图论)时间复杂度链表动态数组邻接表

邻接表是一种用于表示图论中的图的数据结构,它为每个顶点关联一组邻居或关联边。它只存储实际存在的连接,而不会为每一种可能的顶点对单独预留位置。因此,它特别适用于稀疏图,即边数相对于可能的连接数较少的图。虽然名称中带有“表”,邻接表并不一定要使用链表:数组、可调整大小的数组、哈希表及其他容器都可以用来存储邻居。

定义与结构

设图为 G=(V,E)G=(V,E),其中 VV 是顶点集,EE 是边集。对于有向图,顶点 uu 的出边邻接集合表示为

Adj⁡[u]={v∈V:(u,v)∈E}.\operatorname{Adj}[u]=\{v\in V:(u,v)\in E\}.

这一集合记法描述的是简单图。在具体实现中,也可以存储边记录序列,从而允许端点重复,并保存边标识符及其他属性。

邻接表表示通常分为两层:

  • 外层容器,用于定位每个顶点的邻接集合。
  • 内层容器,用于存储该顶点的邻居或边记录。

如果顶点采用连续编号,外层容器可以使用数组(数据结构)。如果顶点以名称或其他键标识,则可以用哈希表将标识符映射到相应的集合。没有邻居的顶点也必须得到表示,例如使用空集合,或在单独的顶点登记表中为其保留条目。

示例

考虑一个无向图,其顶点为 A,B,C,D,EA,B,C,D,E,边为 {A,B}\{A,B\}、{A,C}\{A,C\} 和 {B,D}\{B,D\}:

A: B, C
B: A, D
C: A
D: B
E:

每条边都出现在两个端点各自的集合中。孤立顶点 EE 对应的集合为空。

对于相应的有向边 A→BA\to B、A→CA\to C 和 B→DB\to D,出边邻接表示为:

A: B, C
B: D
C:
D:
E:

邻居的排列顺序通常没有数学意义,但可能影响遍历顺序以及结果的可复现性。

图的变体与边属性

有向图与无向图

在没有自环的无向图中,每条边对应两个邻接条目。因此,顶点的度就是其邻接集合的长度。

在有向图中,出边表记录从某个顶点出发的边。它的长度给出该顶点的出度,而非入度。若要高效访问入边,就需要单独的入边邻接结构或其他索引。如果没有这类结构,查找某个顶点的所有前驱可能需要扫描整个图。

加权图

对于加权图,每个条目可以包含一个邻居及相应的权重:

A: (B, 7), (C, 2)
B: (D, 5)

更一般的边记录还可以包含标识符、标签、容量、时间戳,或指向单独存储的属性的引用。将属性保存在共享的边对象中,可以避免在无向边的两个端点都引用该边时重复存储属性。

平行边与自环

多重图允许同一对端点之间存在多条边。邻接序列可以用独立的记录表示这些边;而仅存储邻居的集合会将它们合并,除非显式保存边的重数或边集合。

自环的处理约定需要格外注意。在无向图中,一个自环对所在顶点的数学意义上的度贡献为二。具体表示时,可以将自环存储两次,以保持度与表长之间的对应关系;也可以只存储一次,并在计算度时单独处理。

空间与操作开销

记 n=∣V∣n=|V|,m=∣E∣m=|E|。通常假设每个顶点条目和每条边记录占用的空间均有固定上界,在此假设下,邻接表使用的空间为

Θ(n+m)\Theta(n+m)

有向图的出边表示存储 mm 个边条目;常规的无向图表示则存储约 2m2m 个。空间复杂度中的顶点项不可忽略,因为孤立顶点也需要得到表示。

各项操作的时间复杂度取决于所选容器。对于未排序的邻接序列,假设访问外层顶点条目所需的时间为常数,则有:

操作 典型开销
枚举 uu 的所有邻居 Θ(deg⁡(u))\Theta(\deg(u))
判断 uu 是否与 vv 相邻 O(deg⁡(u))O(\deg(u))
在链表头部插入一个条目 O(1)O(1)
在可调整大小的数组末尾追加一个条目 均摊 O(1)O(1)
按端点查找并删除一个条目 O(deg⁡(u))O(\deg(u))
枚举所有顶点和边 Θ(n+m)\Theta(n+m)

对于有向图的出边表,这些开销中的 deg⁡(u)\deg(u) 指出度。

上述界限需要附加若干说明:

  • 常数时间插入以无需检查是否已存在重复项为前提。
  • 删除无向边通常需要同时更新两个端点的集合。
  • 删除已知条目可能比定位该条目更快,具体取决于容器以及可用的引用。
  • 删除顶点时,还必须删除与其关联的边。如果只有出边表,定位该顶点的入边可能需要进行完整扫描。
  • 大小可变的边属性和顶点标识符会带来额外的存储需求,不包含在结构本身的 Θ(n+m)\Theta(n+m) 界限内。

因此,“邻接表”规定的是一种表示模式,而不是一套适用于所有实现的操作开销。

实现选择

链表与可调整大小的数组

链表支持在头部进行常数时间插入;如果有合适的引用,也可以支持高效删除。其缺点包括指针开销、内存分配成本,以及节点在内存中分散存放时较差的局部性。

动态数组将邻居连续存储。它通常能提供紧凑的存储和高效的顺序迭代,并受益于CPU 缓存。在末尾追加元素的均摊开销为常数,但删除元素可能需要移动其他元素。如果不必保持顺序,可以用最后一个元素替换待删除的已知元素,再缩小数组。

有序集合与哈希集合

有序邻接数组允许通过二分查找在 O(log⁡deg⁡(u))O(\log \deg(u)) 时间内查找端点,但更新时为了维持顺序,可能需要线性时间的操作。

在合适的哈希假设下,基于哈希的邻居集合可以提供期望常数时间的成员查询和更新操作。它会引入额外的内存开销,迭代时的局部性可能较差,而且如果每个邻居只存储一次,就无法直接保留平行边。

压缩稀疏行存储

压缩稀疏行格式,简称 CSR,将邻接数据紧凑地存入一个偏移量数组和一个连续的邻居数组中。对于编号为 0,…,n−10,\ldots,n-1 的顶点,顶点 uu 的邻居占据以下左闭右开区间:

[offset⁡[u],offset⁡[u+1]).[\operatorname{offset}[u],\operatorname{offset}[u+1]).

偏移量数组包含 n+1n+1 个条目。加权图的表示可以使用一个与邻居数组对应的权重数组来存储权重。

CSR 减少了逐顶点分配内存的开销,并支持高效的顺序处理。它很适合静态图,但图结构发生变化时,可能需要移动数据或重建表示。

在图算法中的应用

邻接表使算法能够直接检查实际存在的边,而不必检查所有可能的顶点对。

假设辅助记录操作均可在常数时间内完成,广度优先搜索和深度优先搜索遍历以邻接表表示的整个图时,运行时间为 O(n+m)O(n+m)。每个顶点的处理次数和每个邻接条目的检查次数都有常数上界。从一个顶点出发的遍历只会访问从该顶点可达的部分,除非再发起其他搜索。

对于最短路径问题,迪ijkstra算法通常将加权邻接表与优先队列配合使用。在边权非负的情况下,采用二叉堆的标准实现,其运行时间为 O((n+m)log⁡n)O((n+m)\log n)。

邻接表还用于拓扑排序、连通分量检测、生成树算法以及网页排名算法。它们广泛出现在道路网络、依赖关系图、社交网络和程序分析结构中。

与其他表示方式的比较

邻接矩阵为每个有序顶点对预留一个位置。因此,常规矩阵需要 Θ(n2)\Theta(n^2) 个条目,支持常数时间的边查询,而枚举某个顶点的邻居通常需要扫描长度为 nn 的一整行。

相比之下,邻接表使用的空间与顶点数和边数之和成正比,枚举邻居所需的时间则与邻居数量成正比。对于稀疏图以及以遍历为主的工作负载,邻接表通常很有吸引力。对于稠密图,矩阵凭借简单的索引、可预测的内存访问以及高效的位压缩表示,可能同样具有竞争力,甚至更为合适。

边列表将所有边存储在由端点对或边记录组成的单一集合中。它便于处理或排序全部边,但如果没有额外建立索引,查找某个顶点的邻居就需要扫描整个集合。

实际选择不仅取决于图的稠密程度,还取决于更新频率、成员查询频率、边属性、内存开销和访问模式。即使一个图在数学意义上是稀疏的,如果每个邻接条目都带有多个指针或单独分配的对象,仍可能产生可观的内存开销。