Adjacency List

Definition / 定义

邻接表：图论与数据结构中用来表示“图（Graph）”的一种方式。对每个顶点（Vertex），保存一个列表，列出与它直接相连的所有邻接顶点（以及可选的边权重、边属性等）。常用于稀疏图，空间效率通常优于邻接矩阵。

Pronunciation / 发音

/əˈdʒeɪsənsi lɪst/

Examples / 例句

We store the graph using an adjacency list.
我们用邻接表来存储这张图。

To run BFS efficiently on a sparse network, represent the graph as an adjacency list and traverse each vertex’s neighbors.
为了在稀疏网络上高效运行广度优先搜索（BFS），可以用邻接表表示图，并遍历每个顶点的邻居节点。

Etymology / 词源

adjacency 来自 adjacent（相邻的），词根含义与“靠近、挨着”有关；在图论中引申为“顶点之间存在边相连的相邻关系”。list 指“列表”。组合起来，adjacency list 字面意思就是“记录相邻关系的列表”，用于按顶点汇总其相邻顶点集合。

Related Words / 相关词

• Adjacency Matrix
• Graph
• Vertex
• Edge
• Neighbor
• BFS
• DFS
• Sparse

Literary Works / 文学作品

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常称 CLRS）——讲解图表示法时广泛使用 adjacency list。
• Algorithms（Robert Sedgewick, Kevin Wayne）——在图章节中以邻接表作为核心实现结构。
• The Algorithm Design Manual（Steven S. Skiena）——讨论图算法与实现时频繁提及邻接表表示。