1. 从“图”说起：为什么我们需要两种存储方式？

如果你刚开始接触数据结构，听到“邻接矩阵”和“邻接表”这两个词，可能会觉得有点抽象。但如果你把它们想象成记录人际关系网的不同方法，一切就清晰了。假设你要记录一个班级里所有同学之间的朋友关系，你会怎么做？

一种最“老实”的方法，是画一张大表格。表格的行和列都是全班同学的名字。如果小明和小红是朋友，你就在“小明”行和“小红”列交叉的格子里打个勾（或者写个1）。这种方法，就是邻接矩阵。它非常直观，想知道任意两个人是不是朋友，看一眼表格就行。但问题也很明显：如果班上50个人，这个表格就有50x50=2500个格子。但实际朋友关系可能只有100对，那么表格里就会有2400个格子是空的（写0）。这造成了巨大的空间浪费，尤其是当这个“班级”规模巨大，比如是一个拥有数亿用户的社交网络时，这种浪费是无法接受的。

另一种更“聪明”的方法，是给每个同学准备一个小本子（链表）。在小明的小本子上，只记录他的朋友：小红、小刚、小芳……想知道小明和谁是不是朋友，就去翻他的小本子。这种方法，就是邻接表。它只存储实际存在的关系，空间利用率高。但如果你想快速知道“小红和小刚是不是朋友”，你就得先翻小红的本子，看看有没有小刚，如果没有，还不能确定，因为小红可能没记，但小刚的本子上记了小红呢？所以你得再翻小刚的本子确认。这种查询效率就不如直接查表格。

你看，这两种方法没有绝对的好坏，只有是否适合。选择哪一种，完全取决于你要解决的“图”是什么样子，以及你主要想用它来做什么操作。是空间金贵，还是查询速度优先？是关系稠密，还是关系稀疏？接下来，我们就深入这两种结构的内部，看看它们具体如何实现，以及在不同场景下该如何抉择。

2. 邻接矩阵：用二维数组构建的关系“全景地图”

邻接矩阵是图最直观、最“暴力”的存储方式。它的核心思想是：用一个V x V的二维数组（矩阵）adjMatrix来表示一个具有V个顶点的图。如果顶点i和顶点j之间存在一条边，那么就在adjMatrix[i][j]的位置上标记一下。

2.1 核心实现与代码剖析

我们以最常见的无权无向图为例。假设我们有4个顶点（0， 1， 2， 3），边的关系是：(0-1)， (0-2)， (1-2)， (2-3)。用邻接矩阵表示如下：

0 1 2 3 0 [0, 1, 1, 0] 1 [1, 0, 1, 0] 2 [1, 1, 0, 1] 3 [0, 0, 1, 0]

矩阵的第i行第j列表示顶点i到顶点j的边。由于是无向图，边 (i, j) 和边 (j, i) 是等价的，所以矩阵是关于主对角线对称的。

用代码实现它的初始化、添加边和查询操作：

class GraphAdjMatrix: def __init__(self, num_vertices): """ 初始化一个 V x V 的矩阵，所有值初始为0。 :param num_vertices: 顶点数量 V """ self.num_vertices = num_vertices # 使用列表推导式创建二维矩阵 self.matrix = [[0] * num_vertices for _ in range(num_vertices)] def add_edge(self, v1, v2): """ 在顶点v1和v2之间添加一条边（无向图）。 :param v1: 顶点1的索引 :param v2: 顶点2的索引 """ # 检查顶点索引是否有效 if 0 <= v1 < self.num_vertices and 0 <= v2 < self.num_vertices: # 无向图，需要设置对称的两个位置 self.matrix[v1][v2] = 1 self.matrix[v2][v1] = 1 else: print(f"错误：顶点索引 {v1} 或 {v2} 超出范围。") def has_edge(self, v1, v2): """ 检查顶点v1和v2之间是否存在边。 :param v1: 顶点1的索引 :param v2: 顶点2的索引 :return: 布尔值，存在边返回True，否则返回False """ if 0 <= v1 < self.num_vertices and 0 <= v2 < self.num_vertices: return self.matrix[v1][v2] == 1 return False def print_matrix(self): """打印邻接矩阵""" for row in self.matrix: print(row) # 使用示例 g = GraphAdjMatrix(4) g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2) g.add_edge(2, 3) print("邻接矩阵：") g.print_matrix() print(f"顶点1和2之间有边吗？ {g.has_edge(1, 2)}") # 输出：True print(f"顶点0和3之间有边吗？ {g.has_edge(0, 3)}") # 输出：False

这段代码清晰地展示了邻接矩阵的基本操作。初始化时分配了固定大小的空间，添加边和查询边的操作都是O(1)的时间复杂度，直接通过数组索引访问，速度快得惊人。

2.2 邻接矩阵的变体与扩展

上面的例子是最简单的情况。在实际应用中，图会有更多属性：

1. 有向图：对于有向边i -> j，我们只设置adjMatrix[i][j] = 1，而adjMatrix[j][i]则保持为0（除非也存在j -> i的边）。此时矩阵不再对称。
2. 带权图：矩阵中存储的不再是0或1，而是边的权重（如距离、成本、流量）。例如，adjMatrix[i][j] = 5表示从i到j的边权重为5。通常用一个特殊值（如float('inf')或一个很大的数）来表示不存在边。
3. 自环：如果允许顶点连接到自身（i -> i），那么adjMatrix[i][i]的位置就会有值。

处理带权图时，初始化矩阵和查询逻辑需要调整：

class WeightedGraphAdjMatrix: def __init__(self, num_vertices): self.num_vertices = num_vertices # 初始化一个“无穷大”矩阵，表示初始时所有顶点都不连通 INF = float('inf') self.matrix = [[INF] * num_vertices for _ in range(num_vertices)] # 顶点到自己的距离通常设为0 for i in range(num_vertices): self.matrix[i][i] = 0 def add_edge(self, v1, v2, weight): if 0 <= v1 < self.num_vertices and 0 <= v2 < self.num_vertices: self.matrix[v1][v2] = weight # 如果是有向图，下面这行注释掉 # self.matrix[v2][v1] = weight def get_weight(self, v1, v2): if 0 <= v1 < self.num_vertices and 0 <= v2 < self.num_vertices: return self.matrix[v1][v2] return None

2.3 邻接矩阵的“阿喀琉斯之踵”：空间复杂度与适用场景

邻接矩阵最大的优点——查询快O(1)，是以巨大的空间开销为代价的。它的空间复杂度是O(V^2)，其中V是顶点数。这意味着，即使图中只有很少的边（稀疏图），你也必须为所有V^2个可能的关系分配内存。

那么，邻接矩阵到底适合用在什么地方？

1. 稠密图：当图的边数量E接近甚至达到最大可能边数V*(V-1)/2（无向图）时，矩阵的空间浪费比例变小，其O(1)的查询优势得以充分发挥。例如，在一些需要频繁判断任意两点是否连通的场景，如小型社交网络的核心圈、某些电路板布线模型。
2. 需要频繁判断边是否存在：如果你的算法核心操作是成千上万次地查询“顶点A和B是否相邻”，邻接矩阵是首选。例如，在图论中实现某些动态规划算法（如Floyd-Warshall全源最短路径算法）时，直接操作矩阵非常方便。
3. 图的规模较小：当顶点数V不大（比如几百个）时，V^2的空间在现代计算机内存中完全可以接受，此时为了编码简单和查询高效，使用矩阵是合理的。

实操心得：在决定使用邻接矩阵前，先问自己两个问题：1. 我的图稠密吗？（边数E是否接近V^2量级？）2. 我的核心算法需要极高频的任意两点邻接查询吗？如果两个答案都是“否”，那么你应该认真考虑邻接表。

3. 邻接表：按需分配的“好友列表”

邻接表采用了完全不同的思路：它不再为所有可能的关系预留空间，而是为每个顶点维护一个列表，这个列表里只存储与该顶点直接相连的邻居顶点。这就像我们每个人的通讯录，只存自己认识的人。

3.1 核心实现：数组+链表的经典组合

最常见的邻接表实现方式是：用一个大小为V的数组，数组的每个元素是一个链表（或动态数组）。数组的索引对应顶点编号，该位置的链表里存储了这个顶点的所有邻居。

继续用刚才的4顶点无向图例子，它的邻接表表示如下：

• 顶点0: [1, 2]
• 顶点1: [0, 2]
• 顶点2: [0, 1, 3]
• 顶点3: [2]

用Python实现，我们可以用列表的列表（List of Lists）来模拟，这比手写链表更简单高效：

class GraphAdjList: def __init__(self, num_vertices): """ 初始化邻接表。 :param num_vertices: 顶点数量 V """ self.num_vertices = num_vertices # 创建一个列表，包含V个空列表 self.adj_list = [[] for _ in range(num_vertices)] def add_edge(self, v1, v2): """ 在顶点v1和v2之间添加一条边（无向图）。 :param v1: 顶点1的索引 :param v2: 顶点2的索引 """ if 0 <= v1 < self.num_vertices and 0 <= v2 < self.num_vertices: # 无向图，需要互相添加 self.adj_list[v1].append(v2) self.adj_list[v2].append(v1) # 注意：这里没有去重。在实际应用中，添加边前可能需要检查是否已存在。 else: print(f"错误：顶点索引 {v1} 或 {v2} 超出范围。") def has_edge(self, v1, v2): """ 检查顶点v1和v2之间是否存在边。 时间复杂度为 O(deg(v1))，其中deg(v1)是顶点v1的度（邻居数）。 :param v1: 顶点1的索引 :param v2: 顶点2的索引 :return: 布尔值 """ if 0 <= v1 < self.num_vertices: # 遍历顶点v1的邻居列表，查找v2 return v2 in self.adj_list[v1] return False def get_neighbors(self, v): """ 获取顶点v的所有邻居。 :param v: 顶点索引 :return: 邻居列表 """ if 0 <= v < self.num_vertices: return self.adj_list[v].copy() # 返回副本以避免外部修改内部数据 return [] def print_list(self): """打印邻接表""" for i, neighbors in enumerate(self.adj_list): print(f"顶点 {i}: {neighbors}") # 使用示例 g = GraphAdjList(4) g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2) g.add_edge(2, 3) print("邻接表：") g.print_list() print(f"顶点1的邻居是：{g.get_neighbors(1)}") # 输出：[0, 2] print(f"顶点1和2之间有边吗？ {g.has_edge(1, 2)}") # 输出：True

3.2 处理有向图与带权图

邻接表同样可以优雅地处理更复杂的图。

• 有向图：添加边v1 -> v2时，只需将v2加入v1的邻居列表，而v2的列表不变。这体现了边的方向性。
• 带权图：邻居列表里不能只存顶点编号了，需要存储一个(邻居顶点， 权重)的元组或一个小对象。

下面是带权有向图的邻接表示例：

class WeightedDirectedGraphAdjList: def __init__(self, num_vertices): self.num_vertices = num_vertices # 每个顶点的列表存储 (目标顶点, 权重) 元组 self.adj_list = [[] for _ in range(num_vertices)] def add_edge(self, from_v, to_v, weight): """添加一条从 from_v 指向 to_v 的带权有向边""" if 0 <= from_v < self.num_vertices and 0 <= to_v < self.num_vertices: self.adj_list[from_v].append((to_v, weight)) else: print("顶点索引错误") def get_outgoing_edges(self, v): """获取从顶点v出发的所有边（目标顶点和权重）""" if 0 <= v < self.num_vertices: return self.adj_list[v].copy() return [] # 使用示例 wg = WeightedDirectedGraphAdjList(3) wg.add_edge(0, 1, 4) # 0 -> 1， 权重4 wg.add_edge(0, 2, 1) # 0 -> 2， 权重1 wg.add_edge(1, 2, 2) # 1 -> 2， 权重2 print("带权有向图的邻接表：") for i, edges in enumerate(wg.adj_list): print(f"顶点 {i} -> {edges}") # 输出： # 顶点 0 -> [(1, 4), (2, 1)] # 顶点 1 -> [(2, 2)] # 顶点 2 -> []

3.3 邻接表的性能特点与适用场景

邻接表的空间复杂度是O(V + E)，其中V是顶点数，E是边数。它只存储实际存在的边，这对于边数远小于V^2的稀疏图来说，节省的空间是巨大的。

它的主要操作复杂度如下：

• 添加边：O(1)（在列表末尾追加）。
• 查询边 (v1, v2) 是否存在：O(deg(v1))，需要遍历v1的邻居列表。在最坏情况下（v1连接了所有其他顶点），复杂度是O(V)。这比邻接矩阵的O(1)慢。
• 遍历某个顶点的所有邻居：O(deg(v1))，这是邻接表的天然优势，因为它直接给出了邻居列表。

邻接表的优势场景：

1. 稀疏图：这是邻接表的主场。社交网络、网页链接关系、交通网络（非枢纽城市之间）等，绝大多数都是稀疏图。
2. 需要遍历顶点邻居的算法：深度优先搜索（DFS）、广度优先搜索（BFS）、Dijkstra最短路径算法、Prim最小生成树算法等。这些算法的核心步骤就是“获取当前顶点的所有邻居并处理”，邻接表做这件事的效率极高。
3. 内存敏感或图规模极大的场景：当顶点数达到百万、千万级别时，V^2的矩阵根本无法装入内存，而V + E的邻接表则可能成为唯一可行的选择。

踩坑实录：在Python中，使用list实现邻接表时，has_edge操作（v2 in list）的平均时间复杂度是O(n)。如果图非常稠密，或者这个查询是算法中的瓶颈，可以考虑将每个顶点的邻居列表换成set（集合），这样has_edge查询可以降到平均O(1)。但代价是set的内存开销略大于list，且元素的插入顺序无法保证。需要根据具体场景权衡。

4. 深度对比与选型指南：不止于空间与时间

到这一步，你可能已经了解了两种结构的基本优劣：矩阵查询快但耗空间，列表省空间但查询慢。但实际选型远比这复杂，我们需要从多个维度进行系统性对比。

4.1 多维度性能对比表格

4.2 从算法角度选择数据结构

你的算法决定了你该如何存储图。

• 如果你要写Floyd-Warshall算法（求所有顶点对之间的最短路径）：这个算法的核心就是对一个二维距离矩阵进行三重循环的松弛操作。使用邻接矩阵作为输入和中间存储是最自然、最高效的选择。虽然你可以用邻接表初始化一个矩阵，但直接操作矩阵代码更清晰。
• 如果你要写Dijkstra或Bellman-Ford算法（单源最短路径）：这些算法需要频繁地“从当前顶点出发，松弛其所有邻居的边”。这正是邻接表的强项——get_neighbors操作高效。使用邻接表，你可以快速迭代所有从该顶点出发的边。如果用矩阵，你不得不遍历一整行（V次）来找到少数几个邻居，效率低下。
• 如果你要写DFS/BFS（图遍历）：同样，核心操作是获取当前顶点的未访问邻居。邻接表可以立即给出所有邻居，而矩阵需要扫描一行。邻接表是图遍历算法的标准选择。
• 如果你要处理动态图（频繁增删边）：两者添加边都很快。但删除边时，矩阵是O(1)，列表是O(deg(v))。如果删除操作非常频繁，矩阵有优势。但更常见的是，动态图伴随着顶点的增删，这时列表的灵活性优势更大。

4.3 一个实战场景的量化分析

假设我们有一个社交网络，有100万用户（V=1,000,000），平均每个用户有200个好友（度 deg=200）。那么总边数 E ≈ (V * deg) / 2 = 1亿（无向图）。

• 邻接矩阵：需要存储一个 1,000,000 x 1,000,000 的矩阵。假设用1字节的布尔值，需要1 TB的内存。这显然不现实。
• 邻接表：需要存储 V 个表头 + E 条边记录。假设每个顶点ID用4字节整数存储。存储边需要2 * E * 4 bytes = 800 MB（无向边存两次）。加上表头开销，总共大约~1 GB内存。这在现代服务器上是可行的。

这个例子清晰地展示了在稀疏的大规模图数据面前，邻接矩阵和邻接表在空间需求上的天壤之别。

选型心法：在做决定前，先估算你的图密度d = E / V^2。如果d大于 0.1（即10%以上的可能边都存在），可以认真考虑矩阵。如果d远小于 0.01（1%），那么邻接表几乎是唯一选择。在0.01到0.1的灰色地带，则需要结合你的核心操作（查询多还是遍历多）和硬件条件来权衡。

5. 进阶话题与工程实践中的考量

掌握了基础，我们来看看在实际项目和工程中，还会遇到哪些问题，以及有哪些优化和变体。

5.1 邻接表的工程实现：不只是List of Lists

上面我们用Python的list套list实现了邻接表，这在小规模图和教学上很好。但在高性能或特定场景下，还有其他选择：

1. 数组+边列表（CSR格式）：这是大规模图计算框架（如GraphLab、PyG）和稀疏矩阵库的常用格式。它使用三个数组：
   • offsets: 长度为V+1，offsets[i]到offsets[i+1]-1是顶点i的邻居在neighbors数组中的范围。
   • neighbors: 按顺序存储所有边的目标顶点。
   • weights(可选): 按相同顺序存储边的权重。
   • 优点：数据完全连续存储，缓存友好，遍历效率极高。缺点：构建复杂，动态增删边代价高。
2. 使用defaultdict(list)或字典：当顶点标识不是连续的整数（比如顶点是字符串用户名）时，无法直接用数组索引。这时可以用字典：graph = {'Alice': ['Bob', 'Charlie'], 'Bob': ['Alice']}。这提供了极大的灵活性，但哈希表的开销比数组大。
3. 使用set代替list：如前所述，如果需要频繁判断边是否存在且不关心邻居顺序，用set存储邻居可以将has_edge操作降到平均O(1)。Python示例：self.adj_list = [set() for _ in range(V)]。

5.2 邻接矩阵的压缩存储

对于稀疏图但又必须用矩阵的场景（比如某些数值计算库的接口要求矩阵），可以采用稀疏矩阵存储格式，如压缩稀疏行（CSR）或坐标列表（COO）。这本质上是在模拟邻接表的高效存储，同时提供矩阵的运算接口。这不是图存储的首选，但在科学与工程计算交叉的领域会遇到。

5.3 处理超大规模图：超出单机内存怎么办？

当图大到一台机器的内存放不下时，无论是矩阵还是列表，单机方案都失效了。这时需要分布式图存储与计算框架，例如：

• 基于BSP模型：像Apache Giraph、Pregel，它们将图的顶点分布到多台机器上，边可能跨机器存储。计算通过“顶点为中心”的迭代进行，消息在机器间传递。
• 基于分布式存储：将图的边列表（邻接表的本质）存储在分布式文件系统（如HDFS）或键值存储中，使用像Spark GraphX这样的框架进行并行计算。
• 图数据库：如Neo4j、JanusGraph，它们专门为存储和查询图数据设计，使用原生图存储格式，并提供了强大的图查询语言（如Cypher）和算法库。

在这些系统中，底层存储抽象可能更复杂，但“邻接关系如何高效存储与访问”仍然是核心问题。邻接表的思想（为每个顶点存储其边）在这些系统中被广泛采用和优化。

5.4 一个综合案例：小型社交网络模拟

假设我们要为一个几千人的公司内部社交网络（“同事圈”）设计后端数据结构。需求是：1. 快速判断两人是否为好友（用于权限检查）。2. 频繁生成“你可能认识的人”（需要遍历好友的好友）。3. 支持动态添加/删除好友关系。

分析：

• 规模几千人，平均好友数几十到上百，是典型的稀疏图。
• 需求1要求高效的边查询。
• 需求2要求高效的邻居遍历。
• 需求3要求支持动态更新。

设计方案： 采用“邻接表 + 索引优化”的混合策略。

• 主存储使用邻接表（List<Set<Integer>>），Set保证了O(1)的平均查询时间，满足了需求1和3。
• Set的无序性不影响需求2的遍历。
• 对于“判断两人是否为好友”这个超高频操作（可能用于每次访问权限验证），可以在业务层增加一个布隆过滤器（Bloom Filter）或Redis缓存进行加速。例如，将好友关系对(A, B)哈希后存入布隆过滤器，查询时先过布隆过滤器，如果返回“可能存在”，再去邻接表里精确查找；如果返回“肯定不存在”，则直接返回否。这用极小的空间和常数时间，拦截了大部分不存在的查询。

这个案例说明，在实际工程中，数据结构的选择不是非此即彼，可以根据核心业务场景进行组合和优化。理解邻接矩阵和邻接表最根本的特性和代价，是做出正确设计和优化的基础。