邻接矩阵与邻接表：图存储结构核心原理与工程选型指南

1. 邻接矩阵与邻接表：图论世界的两种基石

如果你刚开始接触数据结构，尤其是图（Graph）这个庞然大物，一定会遇到两个绕不开的概念：邻接矩阵和邻接表。它们就像是描述人际关系网的两种不同方式。想象一下，你要记录一个班级里所有同学之间的朋友关系。一种方法是画一张巨大的表格，横轴和纵轴都是全班同学的名字，如果A和B是朋友，就在他们交叉的格子里打个勾。另一种方法是给每个同学发一张小卡片，让他只写下自己朋友的名字。前者就是邻接矩阵的思路，后者就是邻接表的思路。这两种方法没有绝对的好坏，但用错了场景，你的程序效率可能会天差地别。今天，我们就来彻底拆解这两种图的存储结构，从底层原理到代码实现，再到实战选型，让你不仅会用，更知道为什么这么用。

2. 邻接矩阵：用二维数组描绘关系网

邻接矩阵是图最直观、最“暴力”的存储方式。它的核心思想非常简单：用一个二维数组（矩阵）来表示图中顶点之间的连接关系。

2.1 核心原理与数据结构设计

对于一个有n个顶点的图，我们创建一个n x n的二维数组matrix。如果顶点i和顶点j之间存在一条边，我们就在matrix[i][j]这个位置上进行标记。对于无向图，这条边是双向的，所以matrix[i][j]和matrix[j][i]都需要标记。对于有向图，则只标记从i指向j的边。

这里的关键在于“标记”的内容，这决定了矩阵能承载的信息量：

• 无权图（简单图）：通常用0或1表示。1表示有边，0表示无边。在C/C++中可以用int或bool数组，在Python中可以用列表的列表。
• 带权图（网络）：矩阵元素存储边的权重。如果i和j无边，则存储一个表示“无穷大”的特殊值（如float('inf')或一个非常大的数），以区别于权重为0的边。

这种设计最大的优点是查询速度极快。判断顶点u和v是否相邻，或者获取边的权重，时间复杂度是O(1)，直接数组下标访问即可。

注意：在实现时，顶点的编号通常从0开始，以方便直接作为数组索引。如果你的业务数据顶点ID不是从0开始的连续整数，需要建立一个从顶点ID到数组索引的映射字典，这一步会增加一些预处理开销。

2.2 代码实现与内存分析

我们以无向无权图为例，看看如何用Python实现一个邻接矩阵类。

class GraphAdjMatrix: def __init__(self, num_vertices): """ 初始化一个具有 num_vertices 个顶点的图。 顶点编号为 0 到 num_vertices-1。 """ self.num_vertices = num_vertices # 初始化一个 n x n 的二维矩阵，所有元素为0 self.matrix = [[0] * num_vertices for _ in range(num_vertices)] def add_edge(self, u, v): """ 在顶点 u 和 v 之间添加一条边（无向图）。 """ if 0 <= u < self.num_vertices and 0 <= v < self.num_vertices: self.matrix[u][v] = 1 self.matrix[v][u] = 1 # 无向图，需要对称设置 else: raise ValueError("顶点索引超出范围") def remove_edge(self, u, v): """ 移除顶点 u 和 v 之间的边。 """ if 0 <= u < self.num_vertices and 0 <= v < self.num_vertices: self.matrix[u][v] = 0 self.matrix[v][u] = 0 else: raise ValueError("顶点索引超出范围") def has_edge(self, u, v): """ 判断顶点 u 和 v 之间是否有边。 """ if 0 <= u < self.num_vertices and 0 <= v < self.num_vertices: return self.matrix[u][v] == 1 else: raise ValueError("顶点索引超出范围") def get_neighbors(self, v): """ 获取顶点 v 的所有邻居顶点。 """ if 0 <= v < self.num_vertices: neighbors = [] for i in range(self.num_vertices): if self.matrix[v][i] == 1: neighbors.append(i) return neighbors else: raise ValueError("顶点索引超出范围") def __str__(self): """以矩阵形式打印图""" return '\n'.join([' '.join(map(str, row)) for row in self.matrix]) # 使用示例 if __name__ == "__main__": g = GraphAdjMatrix(5) # 创建一个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) print("图的邻接矩阵：") print(g) print(f"\n顶点1的邻居：{g.get_neighbors(1)}") print(f"顶点0和4是否有边：{g.has_edge(0, 4)}")

内存占用是邻接矩阵最显著的缺点。无论图中有多少条边，它都需要O(n^2)的空间。对于一个有10000个顶点的稀疏图（边数远小于n^2），比如社交网络中每个人平均认识100个人，那么矩阵中会有10000 * 10000 = 100,000,000个元素，其中绝大部分是0，这造成了巨大的空间浪费。因此，邻接矩阵通常只适用于稠密图（边数接近n^2），或者顶点规模不大但对查询速度要求极高的场景。

2.3 邻接矩阵的典型应用场景与实操心得

邻接矩阵并非一无是处，它在特定场景下优势明显。

场景一：频繁的边存在性查询如果你的算法核心操作是数十万次地询问“顶点A和B是否相连？”，邻接矩阵的O(1)查询时间是无可替代的。例如，在某些图论证明或需要快速进行邻接判断的数学计算中。

场景二：稠密图或小规模图当图的边数非常多，接近完全图时，矩阵的浪费相对较小。或者当顶点数n很小（比如少于500）时，n^2的内存开销在现代计算机上完全可以接受，此时用矩阵实现简单明了。

场景三：需要快速进行矩阵运算图邻接矩阵本身就是一个数学矩阵。某些图算法，如利用矩阵乘法计算路径数量（判断两点间在k步内是否可达），或者一些基于特征值/特征向量的图分析（谱图理论），直接使用矩阵表示是算法本身的要求。

实操心得：

1. 初始化优化：对于带权图，初始化“无穷大”值时，不要用真正的极大值（如1e9），而应该用float('inf')，这样在做加法比较（如if dist[u] + weight < dist[v]）时更安全，避免整数溢出。但在某些只支持整数的环境（如嵌入式C），需要谨慎估算一个足够大的安全值。
2. 空间压缩尝试：对于无向图，邻接矩阵是对称的。你可以选择只存储上三角或下三角矩阵，将空间几乎减半。但这会略微增加代码复杂度，因为访问matrix[i][j]时需要判断i和j的大小关系。除非内存极度紧张，否则不建议在初期优化时引入这种复杂性。
3. 缓存友好性：二维数组在内存中是连续存储的（按行优先），这对CPU缓存预取非常友好。当你遍历某个顶点的所有邻居时（如get_neighbors方法），虽然要遍历一整行，但这一整行数据在内存中是连续的，访问速度很快。这是它相对于邻接表的一个潜在优势。

3. 邻接表：为稀疏图量身定做的存储方案

邻接表的设计哲学是“按需分配”。它不再为所有可能的边预留空间，而是只为每个顶点维护一个列表（链表、动态数组等），列表中只存储与该顶点直接相连的邻居顶点（以及边的权重）。

3.1 核心原理与多种实现形式

邻接表的核心数据结构是一个数组（或字典）adj_list，其长度等于顶点数。adj_list[i]存储的是顶点i的所有出边信息。具体实现有多种选择：

1. 数组的数组（列表的列表）：adj_list[i]是一个Python列表，里面存放着与顶点i相邻的顶点编号。对于带权图，可以存放(neighbor, weight)元组。这是最常用、最直观的实现方式，利用动态数组的灵活性。
2. 链表数组：adj_list[i]是一个链表的头指针。这在C/C++中很常见，可以做到真正的O(1)插入边（在链表头部），但随机访问某个特定邻居的效率是O(degree)。在Python中，我们通常用列表模拟，因为Python列表的尾部追加操作摊销时间复杂度也是O(1)。
3. 字典的数组：adj_list[i]是一个字典，键是邻居顶点，值是边权重。这种方式的优势是可以通过邻居顶点j快速查询边权重（O(1)平均），但内存开销比列表稍大。

邻接表将空间复杂度从O(n^2)降到了O(n + m)，其中n是顶点数，m是边数。这对于稀疏图（m远小于n^2）来说是巨大的优势。

3.2 代码实现与性能权衡

我们实现一个基于“列表的列表”的带权图邻接表，并对比不同操作的复杂度。

class GraphAdjList: def __init__(self, num_vertices): """ 初始化一个具有 num_vertices 个顶点的图（邻接表实现）。 """ self.num_vertices = num_vertices # 初始化一个列表，每个元素是一个空列表，用于存储 (邻居, 权重) self.adj_list = [[] for _ in range(num_vertices)] def add_edge(self, u, v, weight=1): """ 添加一条从 u 到 v 的带权边。 对于无向图，需要调用两次本函数：add_edge(u, v, w) 和 add_edge(v, u, w)。 """ if 0 <= u < self.num_vertices and 0 <= v < self.num_vertices: # 这里简单实现，允许重复边。实际可能需要检查边是否已存在。 self.adj_list[u].append((v, weight)) else: raise ValueError("顶点索引超出范围") def remove_edge(self, u, v): """ 移除从 u 到 v 的边。 注意：对于无向图，需要调用两次。 列表删除需要遍历查找，复杂度O(degree(u))。 """ if 0 <= u < self.num_vertices and 0 <= v < self.num_vertices: # 遍历列表，找到目标边并删除 for i, (neighbor, w) in enumerate(self.adj_list[u]): if neighbor == v: del self.adj_list[u][i] break else: raise ValueError("顶点索引超出范围") def has_edge(self, u, v): """ 判断是否存在从 u 到 v 的边。 需要遍历 u 的邻接列表，复杂度O(degree(u))。 """ if 0 <= u < self.num_vertices and 0 <= v < self.num_vertices: for neighbor, w in self.adj_list[u]: if neighbor == v: return True return False def get_edge_weight(self, u, v): """ 获取从 u 到 v 的边的权重，如果边不存在则返回 None。 """ if 0 <= u < self.num_vertices and 0 <= v < self.num_vertices: for neighbor, w in self.adj_list[u]: if neighbor == v: return w return None def get_neighbors(self, v): """ 获取顶点 v 的所有出边邻居（及权重）。 返回列表的引用，注意不要直接修改内部数据。 """ if 0 <= v < self.num_vertices: return self.adj_list[v] # 返回 (neighbor, weight) 列表 else: raise ValueError("顶点索引超出范围") def __str__(self): """打印邻接表""" result = [] for i in range(self.num_vertices): neighbors_str = ', '.join([f"{n}({w})" for n, w in self.adj_list[i]]) result.append(f"{i}: [{neighbors_str}]") return '\n'.join(result) # 使用示例（有向带权图） if __name__ == "__main__": g = GraphAdjList(5) g.add_edge(0, 1, 4) g.add_edge(0, 4, 2) g.add_edge(1, 2, 3) g.add_edge(1, 3, 1) g.add_edge(1, 4, 5) g.add_edge(2, 3, 6) g.add_edge(3, 4, 7) print("图的邻接表（顶点: [邻居(权重), ...]）：") print(g) print(f"\n顶点1的邻居及权重：{g.get_neighbors(1)}") print(f"是否存在边 1->3：{g.has_edge(1, 3)}") print(f"边 1->4 的权重：{g.get_edge_weight(1, 4)}")

从代码中可以看出邻接表的性能特点：

• 空间：O(n + m)，非常节省。
• 遍历邻居：O(degree(v))，这是遍历图时最频繁的操作，效率很高。
• 查询边(u,v)是否存在：O(degree(u))，需要遍历u的邻居列表。这是它的主要缺点。
• 添加边：O(1)（在列表尾部追加）。
• 删除边：O(degree(u))（需要遍历查找）。

3.3 邻接表的优化变体与实战技巧

基础的列表实现已经能满足大多数需求，但在高性能场景下，我们可以做一些优化。

变体一：使用字典存储邻居将adj_list[i]从列表改为字典{neighbor: weight}。这样可以将has_edge和get_edge_weight操作优化到平均O(1)时间复杂度，代价是字典的哈希表开销比列表稍大，且遍历邻居的顺序是不确定的（Python 3.7+ 字典保持插入顺序，但本质仍是哈希表）。

class GraphAdjDict: def __init__(self, num_vertices): self.num_vertices = num_vertices self.adj_list = [{} for _ in range(num_vertices)] # 每个顶点对应一个字典 def add_edge(self, u, v, weight=1): self.adj_list[u][v] = weight def has_edge(self, u, v): return v in self.adj_list[u] # O(1)平均 def get_edge_weight(self, u, v): return self.adj_list[u].get(v) # O(1)平均

变体二：链式前向星（常用于算法竞赛）这是C/C++中一种极致的空间和时间优化方案。它用三个数组head[], to[], next[], weight[]来模拟链表，所有边被压缩存储在一维数组中。它结合了邻接表的空间效率和数组的缓存局部性，代码稍复杂，但性能极高。Python中因其动态列表本身效率问题，实现前向星的收益不如静态语言明显，但了解其思想很有价值。

实战技巧：

1. 无向图的边添加：在邻接表中，无向边(u, v)需要调用两次add_edge：add_edge(u, v, w)和add_edge(v, u, w)。这是一个常见的错误来源，务必小心。
2. 处理平行边和自环：根据图的具体定义，你可能需要检查并避免平行边（重复边）或允许自环（顶点连接自己）。在add_edge时，可以先检查边是否已存在（has_edge），这会产生O(degree)的开销。如果确定输入没有平行边，可以跳过检查以提升性能。
3. 遍历性能：在运行深度优先搜索（DFS）或广度优先搜索（BFS）时，邻接表的性能远优于邻接矩阵，因为它只遍历实际存在的边。对于稀疏图，这是数量级的差异。
4. 内存与速度的平衡：如果图是静态的（建好后不再修改），可以考虑将每个顶点的邻居列表从Python列表转换为array('I')或numpy数组，甚至排序，这样可以减少内存占用并可能提升缓存命中率，但会牺牲灵活性。

4. 邻接矩阵 vs 邻接表：全方位对比与选型指南

纸上谈兵不如实战对比。下面我们从多个维度系统比较这两种结构，并给出清晰的选型建议。

选型决策流程图：

1. 第一步，看规模与密度：顶点数V是否很大（比如 > 2000）？或者边数E是否远小于V^2（稀疏图）？如果是，优先选择邻接表。
2. 第二步，看核心操作：你的算法是否以每秒数百万次的频率查询任意两个点是否相连？如果是，考虑邻接矩阵。否则，如果核心操作是遍历（如DFS/BFS/最短路径），邻接表更优。
3. 第三步，看开发与维护：项目是否要求极简的代码和逻辑？初期原型是否追求快速实现？如果是，邻接矩阵的简单性有吸引力。但对于长期维护和扩展的项目，邻接表的灵活性通常更好。
4. 第四步，看特殊需求：是否需要做矩阵乘法、特征值计算？如果是，必须用邻接矩阵。

我个人在绝大多数涉及图的开发项目中，首选都是邻接表。只有在处理一些小型的、完全连通的网络拓扑，或者做算法演示和教学时，才会使用邻接矩阵。因为现实世界的数据，从社交网络、网页链接到交通路线，几乎都是稀疏的。

5. 实战演练：用两种结构实现广度优先搜索（BFS）

理论说得再多，不如一行代码。我们分别用邻接矩阵和邻接表来实现图的广度优先搜索算法，并直观感受性能差异。BFS常用于寻找无权图中的最短路径。

假设我们有一个无向无权图，我们需要找到从源点s到目标点t的最短路径（边数最少）。

5.1 基于邻接矩阵的BFS实现

from collections import deque def bfs_adj_matrix(graph_matrix, start, target): """ 使用邻接矩阵进行BFS。 graph_matrix: 二维列表表示的邻接矩阵。 start, target: 起始和目标顶点索引。 返回从start到target的最短距离，如果不可达则返回-1。 """ n = len(graph_matrix) if start == target: return 0 visited = [False] * n distance = [-1] * n # 记录到每个顶点的距离 queue = deque() visited[start] = True distance[start] = 0 queue.append(start) while queue: current = queue.popleft() # 遍历所有顶点，检查是否为邻居 for neighbor in range(n): if graph_matrix[current][neighbor] == 1 and not visited[neighbor]: if neighbor == target: return distance[current] + 1 visited[neighbor] = True distance[neighbor] = distance[current] + 1 queue.append(neighbor) return -1 # 不可达

性能分析：对于每个出队的顶点current，内层循环都要遍历所有n个顶点，检查matrix[current][v]是否为1。因此，总时间复杂度为O(V^2)。即使图很稀疏，它也必须检查所有可能的边。

5.2 基于邻接表的BFS实现

from collections import deque def bfs_adj_list(graph_adj_list, start, target): """ 使用邻接表进行BFS。 graph_adj_list: 列表的列表，graph_adj_list[i]是顶点i的邻居列表。 start, target: 起始和目标顶点索引。 返回从start到target的最短距离，如果不可达则返回-1。 """ n = len(graph_adj_list) if start == target: return 0 visited = [False] * n distance = [-1] * n queue = deque() visited[start] = True distance[start] = 0 queue.append(start) while queue: current = queue.popleft() # 只遍历当前顶点的实际邻居 for neighbor in graph_adj_list[current]: if not visited[neighbor]: if neighbor == target: return distance[current] + 1 visited[neighbor] = True distance[neighbor] = distance[current] + 1 queue.append(neighbor) return -1

性能分析：每个顶点入队出队一次。处理每个顶点时，只遍历它的真实邻居列表。因此，每个顶点和每条边都被访问常数次。总时间复杂度为O(V + E)。对于稀疏图（E ~ V），这近似于O(V)，比矩阵的O(V^2)快得多。

5.3 性能对比实验与结果解读

我们可以构造一个稀疏图（比如顶点数1000，每个顶点平均连接10个邻居，边数约10000）来测试。

import time import random def generate_sparse_graph(n, avg_degree): """生成一个随机的稀疏无向图（邻接表和矩阵）""" adj_list = [[] for _ in range(n)] matrix = [[0]*n for _ in range(n)] for i in range(n): # 为每个顶点随机添加一些边 degree = random.randint(avg_degree-2, avg_degree+2) potential_neighbors = [j for j in range(n) if j != i] neighbors = random.sample(potential_neighbors, min(degree, n-1)) for nb in neighbors: if nb not in adj_list[i]: # 避免重复 adj_list[i].append(nb) adj_list[nb].append(i) matrix[i][nb] = 1 matrix[nb][i] = 1 return adj_list, matrix # 生成图 V = 1000 avg_deg = 10 adj_list, adj_matrix = generate_sparse_graph(V, avg_deg) # 测试BFS性能 start, target = 0, V-1 start_time = time.time() dist_matrix = bfs_adj_matrix(adj_matrix, start, target) time_matrix = time.time() - start_time start_time = time.time() dist_list = bfs_adj_list(adj_list, start, target) time_list = time.time() - start_time print(f"顶点数 V={V}, 平均度数~{avg_deg}") print(f"邻接矩阵BFS耗时: {time_matrix:.4f} 秒， 最短距离: {dist_matrix}") print(f"邻接表BFS耗时 : {time_list:.4f} 秒， 最短距离: {dist_list}") print(f"速度提升倍数: {time_matrix/time_list:.2f}x")

在我的测试中（V=1000），邻接表BFS通常比矩阵BFS快50到100倍。这个差距随着顶点数V的增加呈平方级扩大。这个实验清晰地证明了在稀疏图遍历场景下，邻接表的绝对优势。

6. 进阶话题与常见问题排查

掌握了基础，我们再看一些深入的问题和实际开发中容易踩的坑。

6.1 如何处理动态变化的图？

图不是一成不变的，顶点和边可能会增加或删除。

• 邻接矩阵：增加顶点非常昂贵，需要重新分配一个(n+1)x(n+1)的矩阵并复制数据，O(n^2)。删除顶点同理，需要压缩矩阵。它适合静态图或顶点数固定的图。
• 邻接表：增加顶点只需在adj_list末尾追加一个空列表，O(1)。删除顶点相对复杂，需要从所有其他顶点的邻居列表中移除该顶点，O(V + E)。增加/删除边都是O(1)或O(deg)。对于动态图，邻接表是更可行的选择。

实操心得：如果顶点ID不是连续的整数，使用字典（dict）来存储邻接关系是更好的选择，例如adj_dict = {}，键是顶点标识符（如字符串名称），值是该顶点的邻居集合。这样添加/删除顶点无需重新分配大量内存。

6.2 邻接表如何高效支持“边删除”和“边查询”？

这是邻接表（列表实现）的弱点。有两个优化方向：

1. 使用集合（set）或字典（dict）代替列表：adj_list[i]用set()存储邻居，这样has_edge和remove_edge可以优化到平均O(1)。但遍历邻居时，集合是无序的（虽然Python 3.7+的dict和set有一定顺序，但不保证），且内存开销稍大。
2. 标记删除而非物理删除：如果删除操作不频繁，或者空间不紧张，可以在边的数据结构中增加一个deleted标志位。删除时只标记，在后续遍历时跳过。定期进行垃圾回收。这在某些数据库和文件系统中是常见策略。

6.3 内存优化：从邻接表到CSR/CSC格式

当图的规模巨大（数亿顶点和边），即使使用邻接表，Python对象（列表、元组）的开销也变得不可接受。工业级图计算系统（如NetworkX的底层、GraphBLAS）常使用压缩稀疏行（CSR）或压缩稀疏列（CSC）格式。

• CSR：用三个数组表示图。
  • indptr: 长度为V+1，indptr[i]到indptr[i+1]-1是顶点i的边在indices和data中的范围。
  • indices: 存储所有边的目标顶点。
  • data: （可选）存储边的权重。
• 优点：内存极致紧凑（纯数组），缓存友好，支持快速的按行（源顶点）遍历。缺点：修改图结构（增删边）极其昂贵。

在Python中，你可以使用scipy.sparse.csr_matrix来体验这种格式。它非常适合一次性构建好就不再改变的大型静态图的分析任务。

6.4 常见问题排查表

邻接矩阵和邻接表是理解图论算法的敲门砖，也是工程实践中必须做的第一个设计决策。我的经验是，在不确定的时候，优先选择邻接表，因为它对稀疏图的适应性更好，而现实世界的图数据十有八九是稀疏的。只有在明确需要O(1)边查询、处理稠密小图或进行矩阵运算时，才考虑邻接矩阵。把这两种结构吃透，你就能为任何图相关的问题选择一个坚实的地基。