一、概念
邻接表（Adjacency List）是一种用于表示图（Graph）数据结构的常用方法。它特别适用于稀疏图，即边的数量远小于顶点数量平方的图。邻接表通过为每个顶点维护一个列表来存储与该顶点相邻的顶点，从而高效地表示图的结构。
在图论中，图由顶点（Vertices）和边（Edges）组成。根据边的方向性，图可以分为无向图（Undirected Graph）和有向图（Directed Graph）。邻接表是一种表示图的方法，具体如下：
- 无向图：对于每个顶点，邻接表存储与该顶点直接相连的所有顶点。
- 有向图：对于每个顶点，邻接表存储从该顶点出发的所有边所指向的顶点。
二、原理及优缺点
2.1 原理
邻接表的原理是通过为每个顶点维护一个邻接列表（可以使用链表、数组或其他动态数据结构来实现）来存储图的边信息。具体步骤如下：
- 初始化：创建一个数组或字典，索引或键为顶点，值为邻接列表。
- 添加边：对于无向图，添加边 (u, v) 时，将 v 添加到 u 的邻接列表中，同时将 u 添加到 v 的邻接列表中。对于有向图，添加边 (u, v) 时，仅将 v 添加到 u 的邻接列表中。
- 遍历邻接列表：可以通过遍历每个顶点的邻接列表来访问与该顶点相邻的所有顶点。
2.2 优缺点
优点：
-
空间效率高：对于稀疏图，邻接表比邻接矩阵更节省空间。邻接表的空间复杂度为 O(V + E)，其中 V 是顶点数量，E 是边数量。
-
动态性好：邻接表可以方便地添加或删除边，而不需要重新分配大量内存。
缺点：
-
查找效率低：查找两个顶点之间是否存在边的时间复杂度为 O(V)，因为需要遍历邻接列表。
-
不适合稠密图：对于稠密图，邻接表的空间优势不明显，且查找效率较低。
三、python实现
class Graph:def __init__(self):self.adj_list = {}def add_vertex(self, vertex):if vertex not in self.adj_list:self.adj_list[vertex] = []def add_edge(self, u, v, directed=False):if u not in self.adj_list:self.add_vertex(u)if v not in self.adj_list:self.add_vertex(v)self.adj_list[u].append(v)if not directed:self.adj_list[v].append(u)def display(self):for vertex in self.adj_list:print(f"{vertex}: {' -> '.join(map(str, self.adj_list[vertex]))}")# 示例用法
graph = Graph()
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'D')
graph.add_edge('C', 'D')
graph.display()四、与邻接矩阵的对比
邻接矩阵适用于边的数量接近顶点数量平方的图，尤其是结构不经常变化的静态图。邻接表则适用于边的数量远小于顶点数量平方的图，尤其是需要频繁添加或删除边的动态图。
| 特性 | 邻接表 | 邻接矩阵 |
|---|---|---|
| 空间复杂度 | O(V+E) | O(V²) |
| 查找边的效率 | O(V) | O(1) |
| 添加边的效率 | O(1) | O(1) |
| 删除边的效率 | O(V) | O(1) |
| 动态性 | 高 | 低 |
| 适用图 | 稀疏图 | 稠密图 |
| 实现复杂度 | 较低 | 较高 |
