邻接表Adjacency list
为每个顶点保存相邻顶点或出边的集合，可用数组、链表等容器实现。
- 核心约束
- 邻接项须指向有效顶点；无向边通常在两个端点各保存一项。
- 适用问题
- 稀疏图、调用关系、计算图和需要逐边遍历的图算法。
- 边界与取舍
- 无额外索引时判断一条边是否存在需扫描该顶点的邻接项；删除和去重成本取决于容器。
常见操作#
V 为顶点数，E 为边数；邻居保存在普通链表或动态数组中。
| 操作 | 时间复杂度 | 条件与说明 |
|---|---|---|
| 构建 | 输入是顶点和边列表，每条边追加到相应列表。 | |
| 查询有向边 (u, v) | 在 u 的邻居列表中定位 v；不维护额外邻居索引。 | |
| 删除边 (u, v) | 有向图 ；无向图 | 无向边保存在两端列表，需要分别寻找和删除；逆边句柄可减少其中的定位工作。 |
| 插入边 | 摊还 | 顶点已存在、不检查重边，使用链表头插或动态数组尾插。 |
| 枚举 u 的邻居 | 成本包含输出每个邻接项。 | |
| 遍历全部邻接项 | 访问每个顶点及其邻接列表。 |
时间与空间#
- 时间复杂度
- 邻居枚举
- 存储空间
若改用排序数组、哈希集合或树保存邻居，查边和更新成本必须重新注明。
工程中的应用#
2 个案例 · 附源码HNSW 从稀疏上层快速定位区域，再在底层扩大候选搜索。
附源码片段 · 检索与计算
Git 的拓扑历史遍历记录尚未输出的子提交数量；只有相关子提交都已处理，父提交才进入可输出集合。
附源码片段 · 图处理与编译
基础原理参考资料
Open Data Structures · AdjacencyLists逐项说明构造、加边、删边、查边及出入边列表。