【如何建立邻接表】邻接表是一种常用的数据结构，用于表示图的结构。它通过为每个顶点维护一个列表，记录与该顶点相连的所有其他顶点，从而高效地存储和操作图中的边信息。在实际编程中，邻接表广泛应用于图的遍历、最短路径算法等场景。
以下是对“如何建立邻接表”的总结性说明，并附有相关表格以帮助理解。
一、邻接表的基本概念
邻接表由多个链表或列表组成，每个顶点对应一个列表，其中包含与该顶点相邻的所有顶点。这种结构适合表示稀疏图（即边的数量远小于顶点数的平方）。
- 优点：
- 存储空间更高效。
- 支持快速访问相邻顶点。
- 缺点：
- 查询两个顶点之间是否有边需要遍历列表，效率较低。
二、建立邻接表的步骤
1. 确定图的顶点数量：例如，图中有 `n` 个顶点。
2. 初始化邻接表结构：通常使用数组或字典来保存每个顶点的邻接列表。
3. 逐条添加边信息：对于每一条边 `(u, v)`，将 `v` 添加到 `u` 的邻接列表中（如果是无向图，则同时将 `u` 添加到 `v` 的邻接列表中）。
4. 处理权重（可选）：如果图是带权图，可以将邻接表中的元素改为元组形式，如 `(目标顶点, 权重)`。
三、示例说明
假设有一个无向图，包含顶点 `A`, `B`, `C`, `D`，边如下：
- A-B
- A-C
- B-D
- C-D
邻接表表示如下：
| 顶点 | 邻接顶点 |
| A | B, C |
| B | A, D |
| C | A, D |
| D | B, C |
四、代码实现（Python 示例）
```python
初始化邻接表（字典）
adj_list = {
'A': [],
'B': [],
'C': [],
'D': [
}
添加边
def add_edge(u, v):
adj_list[u].append(v)
adj_list[v].append(u) 无向图，双向添加
示例添加边
add_edge('A', 'B')
add_edge('A', 'C')
add_edge('B', 'D')
add_edge('C', 'D')
打印邻接表
for vertex in adj_list:
print(f"{vertex}: {adj_list[vertex]}")
```
五、邻接表的适用场景
| 场景 | 是否适用 | 说明 |
| 稀疏图 | ✅ | 空间利用率高 |
| 图的遍历 | ✅ | 可快速访问邻接点 |
| 最短路径算法 | ✅ | 如 BFS、DFS、Dijkstra 等 |
| 大规模图 | ✅ | 比邻接矩阵更节省内存 |
六、总结
邻接表是一种灵活且高效的图结构表示方式，特别适用于边数较少的图。通过合理设计数据结构，可以轻松实现对图的存储、查询和操作。在实际应用中，根据图的类型（有向/无向、带权/不带权）选择合适的邻接表实现方式，能够显著提升程序的性能和可读性。