【如何建立邻接表】在图的表示方法中，邻接表是一种常用且高效的存储结构。它通过为每个顶点维护一个列表，记录与该顶点相邻的所有顶点，从而节省空间并便于遍历。以下是关于如何建立邻接表的详细总结。
一、邻接表的基本概念
邻接表（Adjacency List）是一种用于表示图的结构，适用于有向图和无向图。其核心思想是：每个顶点对应一个链表或列表，其中包含所有与该顶点相邻的顶点。
- 优点：
- 空间效率高，尤其适合稀疏图。
- 遍历方便，可快速找到邻接顶点。
- 缺点：
- 查询两个顶点之间是否有边时，需要遍历列表，效率较低。
二、建立邻接表的步骤
1. 确定图的顶点数量和边的数量
2. 初始化一个列表或数组，每个元素对应一个顶点
3. 遍历每一条边，将对应的顶点加入到邻接表中
三、邻接表的构建示例
以一个简单的无向图为例：
- 顶点集合：{A, B, C, D}
- 边集合：{(A,B), (A,C), (B,D), (C,D)}
构建过程如下：
| 步骤 | 操作 | 结果 |
| 1 | 初始化邻接表 | 表格为空 |
| 2 | 处理边 (A,B) | A 的邻接表添加 B，B 的邻接表添加 A |
| 3 | 处理边 (A,C) | A 的邻接表添加 C，C 的邻接表添加 A |
| 4 | 处理边 (B,D) | B 的邻接表添加 D，D 的邻接表添加 B |
| 5 | 处理边 (C,D) | C 的邻接表添加 D，D 的邻接表添加 C |
四、邻接表的表示形式
| 顶点 | 邻接顶点列表 |
| A | B, C |
| B | A, D |
| C | A, D |
| D | B, C |
五、代码实现（Python 示例）
```python
定义邻接表
adj_list = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C'
}
打印邻接表
for vertex in adj_list:
print(f"{vertex} -> {', '.join(adj_list[vertex])}")
```
六、小结
| 项目 | 内容 |
| 用途 | 存储图的结构，便于遍历和查找邻接顶点 |
| 优点 | 空间利用率高，操作灵活 |
| 缺点 | 查找边的存在性效率低 |
| 应用场景 | 图的遍历、最短路径算法等 |
通过以上步骤和示例，可以清晰地理解如何建立邻接表，并根据实际需求进行调整和扩展。
