Python 邻接表

图结构建模核心工具|系统掌握邻接表原理、实现与实战应用

⚡ 邻接表:图结构建模的轻量级核心

邻接表(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 的邻接表。

⚙️ 邻接表设计:从抽象到具体

设计邻接表需明确三个核心维度:

  1. 图的类型:有向图(Directed Graph)还是无向图(Undirected Graph)?带权(Weighted)还是无权(Unweighted)?
  2. 顶点标识方式:整数(0,1,2,...)、字符串("A","B","C",...)还是自定义对象?
  3. 邻接结构组织:使用 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²)。

⚡ 性能优化:邻接表实战技巧

优化邻接表需兼顾时间与空间,以下为高频技巧:

  1. 预分配列表索引:顶点为连续整数时,用列表替代字典:
    graph = [[] for _ in range(n)],查询速度提升 30%~50%
  2. 冻结不可变数据:对静态图,将邻接表转为 tuple:
    graph = tuple(tuple(neighbors) for neighbors in graph),节省内存并加速迭代
  3. 位运算优化:顶点数 ≤ 64 时,用整数位掩码表示邻接集:
    adj[u] = (1 << v1) | (1 << v2) | ...,交集、并集操作快 10 倍
  4. 缓存度数:频繁查询 degree 时,额外维护 self.degree = {}
  5. 稀疏矩阵压缩:超大规模图(V > 10⁷)时,用 scipy.sparse.csr_matrix 存储邻接表
位掩码邻接表示例(顶点0~7)
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 位机器上最优)。

⚠️ 常见错误与排查指南

邻接表使用中高频错误如下:

  1. 忘记添加反向边(无向图):
    添加边 u-v 时,仅执行 adj[u].append(v),导致后续遍历漏掉 v→u 路径。
    ✅ 解决:无向图必须双向添加,或封装 add_edge 方法统一处理。
  2. 顶点未注册:
    直接操作邻接表(如 graph[u].append(v)),但未将 u/v 加入 vertices 集合,导致 len(graph) 不准。
    ✅ 解决:使用 add_vertex/add_edge 方法统一管理。
  3. 邻接表与顶点集不同步:
    删除顶点 u 后,未清理其他顶点邻接表中的 u。
    ✅ 解决:删除顶点时,扫描所有邻接表移除 u,或惰性删除(标记为无效)。
  4. 权重未初始化:
    带权图中,用无权方式添加边(graph[u].append(v)),导致 Dijkstra 报错。
    ✅ 解决:显式指定 weighted=True,或在 add_edge 时强制传 weight。
  5. 迭代时修改结构:
    遍历 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周)

进阶阶段(2~4周)

实战阶段(1个月+)

推荐资源
  • 《算法导论》第22~24章:图论基础与最短路径
  • LeetCode 图专题:第207(课程表)、785(二分图)、210(课程表II)
  • NetworkX 库源码:学习工业级图算法实现
  • GitHub 项目:python-graphs(简单图库)、graspologic(统计图学习)