邻接表是图数据结构的一种高效表示方法，特别适合表示稀疏图。下面我将用 Python 详细讲解邻接表的多种实现方式、操作方法和实际应用。

一、邻接表基础概念

邻接表的核心思想是为图中的每个顶点维护一个列表，存储与该顶点直接相连的所有邻接顶点。

邻接表 vs 邻接矩阵

特性	邻接表	邻接矩阵
空间复杂度	O(V+E)	O(V²)
检查两顶点是否相邻	O(degree(V))	O(1)
获取所有邻接点	O(1)	O(V)
添加边	O(1)	O(1)
删除边	O(degree(V))	O(1)

二、Python 邻接表实现方式

1. 基础列表实现（无向图）

class Graph:def __init__(self, num_vertices):self.num_vertices = num_verticesself.adj_list = [[] for _ in range(num_vertices)]def add_edge(self, u, v):"""添加无向边 u-v"""self.adj_list[u].append(v)self.adj_list[v].append(u)def print_graph(self):for i in range(self.num_vertices):print(f"顶点 {i} 的邻接点: {self.adj_list[i]}")# 使用示例
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.print_graph()

2. 使用 defaultdict（动态顶点）

python

复制

from collections import defaultdictclass Graph:def __init__(self):self.adj_list = defaultdict(list)def add_edge(self, u, v):"""添加无向边 u-v"""self.adj_list[u].append(v)self.adj_list[v].append(u)def print_graph(self):for vertex in self.adj_list:print(f"顶点 {vertex} 的邻接点: {self.adj_list[vertex]}")# 使用示例
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.print_graph()

3. 加权图实现

python

复制

from collections import defaultdictclass WeightedGraph:def __init__(self):self.adj_list = defaultdict(list)def add_edge(self, u, v, weight):"""添加加权无向边 u-v"""self.adj_list[u].append((v, weight))self.adj_list[v].append((u, weight))def print_graph(self):for vertex in self.adj_list:connections = [f"{v}({w})" for v, w in self.adj_list[vertex]]print(f"顶点 {vertex} 的连接: {', '.join(connections)}")# 使用示例
wg = WeightedGraph()
wg.add_edge(0, 1, 4)
wg.add_edge(0, 2, 1)
wg.add_edge(1, 2, 2)
wg.add_edge(1, 3, 5)
wg.print_graph()

三、邻接表的高级操作

1. 有向图实现

python

复制

class DirectedGraph:def __init__(self, num_vertices):self.num_vertices = num_verticesself.adj_list = [[] for _ in range(num_vertices)]def add_edge(self, u, v):"""添加有向边 u→v"""self.adj_list[u].append(v)def reverse(self):"""反转图中所有边的方向"""reversed_graph = DirectedGraph(self.num_vertices)for u in range(self.num_vertices):for v in self.adj_list[u]:reversed_graph.add_edge(v, u)return reversed_graphdef print_graph(self):for i in range(self.num_vertices):print(f"顶点 {i} 指向: {self.adj_list[i]}")# 使用示例
dg = DirectedGraph(4)
dg.add_edge(0, 1)
dg.add_edge(0, 2)
dg.add_edge(1, 2)
dg.add_edge(2, 0)
dg.add_edge(2, 3)
dg.print_graph()

2. 删除边和顶点

python

复制

class AdvancedGraph:def __init__(self):self.adj_list = defaultdict(list)def add_edge(self, u, v):self.adj_list[u].append(v)self.adj_list[v].append(u)def remove_edge(self, u, v):"""删除无向边 u-v"""if v in self.adj_list[u]:self.adj_list[u].remove(v)self.adj_list[v].remove(u)def remove_vertex(self, u):"""删除顶点及其所有边"""for v in self.adj_list[u]:self.adj_list[v].remove(u)del self.adj_list[u]def print_graph(self):for vertex in self.adj_list:print(f"顶点 {vertex} 的邻接点: {self.adj_list[vertex]}")# 使用示例
ag = AdvancedGraph()
ag.add_edge(0, 1)
ag.add_edge(0, 2)
ag.add_edge(1, 2)
ag.add_edge(2, 3)
print("原始图:")
ag.print_graph()ag.remove_edge(1, 2)
print("\n删除边1-2后:")
ag.print_graph()ag.remove_vertex(2)
print("\n删除顶点2后:")
ag.print_graph()

四、邻接表的实际应用

1. 广度优先搜索(BFS)

python

复制

from collections import dequedef bfs(graph, start):visited = set()queue = deque([start])visited.add(start)while queue:vertex = queue.popleft()print(vertex, end=" ")for neighbor in graph.adj_list[vertex]:if neighbor not in visited:visited.add(neighbor)queue.append(neighbor)# 使用示例
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)print("BFS遍历从顶点2开始:")
bfs(g, 2)

2. 深度优先搜索(DFS)

python

复制

def dfs(graph, start, visited=None):if visited is None:visited = set()visited.add(start)print(start, end=" ")for neighbor in graph.adj_list[start]:if neighbor not in visited:dfs(graph, neighbor, visited)# 使用示例
print("\nDFS遍历从顶点2开始:")
dfs(g, 2)

3. 检测图中是否有环

python

复制

def has_cycle(graph):visited = set()def dfs_util(vertex, parent):visited.add(vertex)for neighbor in graph.adj_list[vertex]:if neighbor not in visited:if dfs_util(neighbor, vertex):return Trueelif neighbor != parent:return Truereturn Falsefor vertex in graph.adj_list:if vertex not in visited:if dfs_util(vertex, -1):return Truereturn False# 使用示例
cycle_graph = Graph(3)
cycle_graph.add_edge(0, 1)
cycle_graph.add_edge(1, 2)
cycle_graph.add_edge(2, 0)no_cycle_graph = Graph(3)
no_cycle_graph.add_edge(0, 1)
no_cycle_graph.add_edge(1, 2)print("\n图中是否有环:")
print("cycle_graph:", has_cycle(cycle_graph))
print("no_cycle_graph:", has_cycle(no_cycle_graph))

五、性能优化技巧

1. ​使用集合代替列表​：如果需要频繁检查边的存在性

   python

   复制

   self.adj_list = defaultdict(set)  # 使用集合存储邻接点

2. ​预分配空间​：已知顶点数量时

   python

   复制

   self.adj_list = [None] * num_vertices
   for i in range(num_vertices):self.adj_list[i] = []

3. ​使用更高效的数据结构​：如 array.array 或 numpy.ndarray 处理大型图

4. ​并行处理​：对大型图的操作可以使用多线程/多进程

六、常见问题解答

​Q: 如何表示带权重的有向图？​​

A: 可以使用字典存储权重信息：

python

复制

class WeightedDirectedGraph:def __init__(self):self.adj_list = defaultdict(list)def add_edge(self, u, v, weight):self.adj_list[u].append((v, weight))def print_graph(self):for vertex in self.adj_list:connections = [f"{v}({w})" for v, w in self.adj_list[vertex]]print(f"顶点 {vertex} 指向: {', '.join(connections)}")

​Q: 如何处理顶点不是整数的情况？​​

A: 可以使用字典映射：

python

复制

class NamedGraph:def __init__(self):self.adj_list = defaultdict(list)self.vertex_index = {}self.index_vertex = {}self.counter = 0def add_vertex(self, name):if name not in self.vertex_index:self.vertex_index[name] = self.counterself.index_vertex[self.counter] = nameself.counter += 1def add_edge(self, u_name, v_name):self.add_vertex(u_name)self.add_vertex(v_name)u = self.vertex_index[u_name]v = self.vertex_index[v_name]self.adj_list[u].append(v)self.adj_list[v].append(u)def print_graph(self):for i in range(self.counter):name = self.index_vertex[i]neighbors = [self.index_vertex[v] for v in self.adj_list[i]]print(f"顶点 {name} 的邻接点: {neighbors}")

通过以上详细的 Python 实现，你应该能够全面掌握邻接表的构建方法和各种操作技巧。根据你的具体应用场景，可以选择最适合的实现方式。