⚡ 邻接表:图结构建模的轻量级核心
邻接表(Adjacency List)是图论与图数据结构中表示稀疏图最常用、最高效的方式之一。在 Python 中,邻接表通常以字典(dict)或列表(list)嵌套结构实现,其本质是为每个顶点维护一个邻接顶点列表,从而以空间换时间,实现快速的邻居查询与边遍历。
相较于邻接矩阵的 O(V²) 空间复杂度,邻接表仅需 O(V + E) 空间(V为顶点数、E为边数),在稀疏图(E ≪ V²)场景下优势显著。例如社交网络中用户关系图(每人平均好友数约100,总用户1亿),邻接矩阵需约 8×10¹⁵ 字节(8 PB),而邻接表仅需约 800 MB,差距达百万倍。
邻接表不仅结构简洁,还天然契合图遍历算法(BFS/DFS)、最短路径(Dijkstra/Floyd)、最小生成树(Prim/Kruskal)等经典算法的实现范式。掌握邻接表的构造、查询与更新,是构建图计算系统、推荐引擎、知识图谱、网络拓扑分析等应用的基石。
特别说明:邻接表的“邻接”二字并非指几何邻近,而是指“存在直接边连接”——即若顶点 u 与 v 之间存在边 (u, v),则 v 属于 u 的邻接表,u 属于 v 的邻接表(无向图);若为有向图,则仅 v 属于 u 的邻接表。
⚙️ 邻接表设计:从抽象到具体
设计邻接表需明确三个核心维度:
- 图的类型:有向图(Directed Graph)还是无向图(Undirected Graph)?带权(Weighted)还是无权(Unweighted)?
- 顶点标识方式:整数(0,1,2,...)、字符串("A","B","C",...)还是自定义对象?
- 邻接结构组织:使用 dict[int, list[int]]、dict[str, list[str]]、defaultdict(list) 还是自定义类?
① 无权无向图(整数顶点)
graph = {
0: [1, 2],
1: [0, 2, 3],
2: [0, 1, 3],
3: [1, 2]
}
② 带权有向图(字符串顶点)
graph = {
'A': [('B', 5), ('C', 2)],
'B': [('C', 1), ('D', 4)],
'C': [('D', 3)],
'D': []
}
③ 使用 defaultdict 简化插入
from collections import defaultdict
graph = defaultdict(list)
# 添加边 A→B(权3)
graph['A'].append(('B', 3))
# 添加无向边
graph['B'].append(('A', 3))
设计时还需注意:若顶点可能不连续(如跳过编号 3),应避免使用列表索引;若需频繁判断边是否存在,可额外维护 set 边集(空间换时间);若顶点动态增删,应采用可变容器(如 list)而非 tuple。
📊 邻接表 vs 邻接矩阵:关键差异对比
| 特性 | 邻接表 | 邻接矩阵 |
|---|---|---|
| 空间复杂度 | O(V + E) | O(V²) |
| 判断边存在 | O(degree(u)) | O(1) |
| 获取所有邻居 | O(degree(u)) | O(V) |
| 添加顶点 | O(1) | O(V²)(需重建矩阵) |
| 添加边 | O(1) | O(1) |
| 删除顶点 | O(V + E)(需扫描全图) | O(V²)(需重建) |
| 适合场景 | 稀疏图(E ≈ V)、动态图 | 稠密图(E ≈ V²)、静态图 |
举个典型场景:微博关注关系图(1亿用户,每人关注200人),E ≈ 2×10⁹,V = 10⁸,E/V² ≈ 0.0002%,属极度稀疏图。邻接矩阵需约 80 TB 内存,而邻接表仅需约 16 GB(按每条边8字节计),差距达5000倍。
【经验法则】当 E < 0.1 × V² 时,优先考虑邻接表;当图需频繁插入/删除顶点时,邻接表优势更明显。
🛠️ Python 邻接表实现:从零构建完整图类
以下是一个支持有向/无向、带权/无权的通用图类实现,兼顾扩展性与实用性:
from collections import defaultdict
class Graph:
def __init__(self, directed=True, weighted=False):
self.adj = defaultdict(list) # 邻接表:顶点 → [(邻居, 权重)] 或 [邻居]
self.directed = directed
self.weighted = weighted
self.vertices = set() # 所有顶点集合
def add_vertex(self, v):
self.vertices.add(v)
def add_edge(self, u, v, weight=None):
self.vertices.update([u, v])
if self.weighted:
self.adj[u].append((v, weight))
if not self.directed:
self.adj[v].append((u, weight))
else:
self.adj[u].append(v)
if not self.directed:
self.adj[v].append(u)
def get_neighbors(self, v):
if self.weighted:
return [nb for nb, _ in self.adj[v]]
return self.adj[v]
def get_edge_weight(self, u, v):
if not self.weighted:
raise ValueError("Graph is unweighted")
for nb, w in self.adj[u]:
if nb == v:
return w
raise KeyError(f"Edge {u}->{v} not found")
def __contains__(self, v):
return v in self.vertices
def __len__(self):
return len(self.vertices)
① 构建带权无向图
g = Graph(directed=False, weighted=True)
g.add_edge('A', 'B', 5)
g.add_edge('A', 'C', 2)
g.add_edge('B', 'C', 1)
print(g.get_neighbors('A')) # → ['B', 'C']
print(g.get_edge_weight('B', 'C')) # → 1
② 构建无权有向图
g = Graph(directed=True)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 0)
print(1 in g) # → True
print(g.get_neighbors(1)) # → [2]
注意:上述实现中,get_edge_weight 在边不存在时抛出 KeyError,实际项目中建议返回 None 或默认值;若需支持重边(多条边连接同一对顶点),应将邻接表改为 list[list[tuple]],但会增加复杂度。
🚀 图算法实战:基于邻接表的经典算法
邻接表是图遍历与路径算法的天然搭档。以下展示三大核心算法在邻接表上的实现:
BFS 与 DFS 实现
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
order = []
while queue:
v = queue.popleft()
order.append(v)
for nb in graph.get_neighbors(v):
if nb not in visited:
visited.add(nb)
queue.append(nb)
return order
def dfs(graph, start, visited=None, order=None):
if visited is None: visited = set()
if order is None: order = []
visited.add(start)
order.append(start)
for nb in graph.get_neighbors(start):
if nb not in visited:
dfs(graph, nb, visited, order)
return order
示例:对图 g(A-B:5, A-C:2, B-C:1)执行 BFS:
g = Graph(directed=False, weighted=True)
g.add_edge('A', 'B', 5)
g.add_edge('A', 'C', 2)
g.add_edge('B', 'C', 1)
print(bfs(g, 'A')) # → ['A', 'B', 'C'] 或 ['A', 'C', 'B']
Dijkstra 最短路径算法
import heapq
def dijkstra(graph, start):
dist = {v: float('inf') for v in graph.vertices}
dist[start] = 0
pq = [(0, start)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]: continue
for v, w in graph.adj[u]: # 邻接表直接遍历邻居
new_dist = dist[u] + w
if new_dist < dist[v]:
dist[v] = new_dist
heapq.heappush(pq, (new_dist, v))
return dist
示例:求 A 到所有点的最短距离:
dist = dijkstra(g, 'A')
print(dist) # → {'A': 0, 'B': 3, 'C': 2} # A→B→C=3, A→C=2
连通分量:并查集(Union-Find)
class UnionFind:
def __init__(self, vertices):
self.parent = {v: v for v in vertices}
self.rank = {v: 0 for v in vertices}
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 路径压缩
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return
if self.rank[px] < self.rank[py]: px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]: self.rank[px] += 1
def connected_components(graph):
uf = UnionFind(graph.vertices)
for u in graph.adj:
for v, _ in graph.adj[u]:
uf.union(u, v)
return [v for v in graph.vertices if uf.find(v) == v]
【关键点】Dijkstra 算法中,邻接表使每个顶点的邻居遍历仅需 O(degree(u)),总时间复杂度 O((V + E) log V),优于邻接矩阵的 O(V²)。
⚡ 性能优化:邻接表实战技巧
优化邻接表需兼顾时间与空间,以下为高频技巧:
- 预分配列表索引:顶点为连续整数时,用列表替代字典:
graph = [[] for _ in range(n)],查询速度提升 30%~50% - 冻结不可变数据:对静态图,将邻接表转为 tuple:
graph = tuple(tuple(neighbors) for neighbors in graph),节省内存并加速迭代 - 位运算优化:顶点数 ≤ 64 时,用整数位掩码表示邻接集:
adj[u] = (1 << v1) | (1 << v2) | ...,交集、并集操作快 10 倍 - 缓存度数:频繁查询 degree 时,额外维护
self.degree = {} - 稀疏矩阵压缩:超大规模图(V > 10⁷)时,用 scipy.sparse.csr_matrix 存储邻接表
graph = [0] * 8 # 8个顶点
# 边 0→1, 0→3, 0→5
graph[0] = (1 << 1) | (1 << 3) | (1 << 5) # 二进制: 00101010 = 42
# 检查边 0→3 是否存在
if graph[0] & (1 << 3):
print("Edge exists") # → True
# 获取所有邻居
neighbors = [i for i in range(8) if graph[0] & (1 << i)] # → [1, 3, 5]
【注意】位掩码仅适用于顶点数 ≤ 64 的场景(Python int 无限精度,但位运算在 64 位机器上最优)。
⚠️ 常见错误与排查指南
邻接表使用中高频错误如下:
- 忘记添加反向边(无向图):
添加边 u-v 时,仅执行adj[u].append(v),导致后续遍历漏掉 v→u 路径。
✅ 解决:无向图必须双向添加,或封装 add_edge 方法统一处理。 - 顶点未注册:
直接操作邻接表(如graph[u].append(v)),但未将 u/v 加入 vertices 集合,导致 len(graph) 不准。
✅ 解决:使用 add_vertex/add_edge 方法统一管理。 - 邻接表与顶点集不同步:
删除顶点 u 后,未清理其他顶点邻接表中的 u。
✅ 解决:删除顶点时,扫描所有邻接表移除 u,或惰性删除(标记为无效)。 - 权重未初始化:
带权图中,用无权方式添加边(graph[u].append(v)),导致 Dijkstra 报错。
✅ 解决:显式指定weighted=True,或在 add_edge 时强制传 weight。 - 迭代时修改结构:
遍历for nb in adj[u]时,向 adj[u] 添加新元素,导致死循环。
✅ 解决:复制迭代for nb in list(adj[u])。
- 打印图结构:
print(dict(graph.adj))检查边是否双向对称 - 验证连通性:
len(set(bfs(graph, start))) == len(graph.vertices) - 统计稀疏度:
edge_count = sum(len(neighbors) for neighbors in graph.adj.values())
📚 学习路径:从入门到精通
掌握邻接表需分阶段实践:
入门阶段(1~2周)
- 用列表/dict 手写邻接表,理解基本结构
- 实现 BFS/DFS 遍历,输出节点访问顺序
- 用邻接表构建迷宫图(网格图),求起点到终点路径
进阶阶段(2~4周)
- 实现 Dijkstra、Floyd-Warshall、Prim 算法
- 对比邻接表与邻接矩阵在稠密/稀疏图上的性能差异
- 构建社交网络图(顶点=用户,边=关注关系),统计中心性指标
实战阶段(1个月+)
- 集成邻接表至 Web 服务(Flask/FastAPI),提供图 API
- 用 Redis SortedSet 实现动态邻接表(实时更新关注关系)
- 优化超大规模图(10⁷ 顶点):分片存储 + 并查集 + 外部排序
- 《算法导论》第22~24章:图论基础与最短路径
- LeetCode 图专题:第207(课程表)、785(二分图)、210(课程表II)
- NetworkX 库源码:学习工业级图算法实现
- GitHub 项目:python-graphs(简单图库)、graspologic(统计图学习)