邻接矩阵实战：5分钟搞懂有向图和有权图的存储与遍历

邻接矩阵实战：5分钟搞懂有向图和有权图的存储与遍历

最近在帮一个朋友优化他的社交网络推荐算法原型时，我发现他还在用字典套列表的方式来表示用户关系图。当节点数超过一千，查询“用户A是否关注了用户B”这种简单操作，性能瓶颈就非常明显。我建议他试试邻接矩阵，他第一反应是：“那不是又占内存又难用吗？” 这其实是个很普遍的误解。邻接矩阵绝非过时的数据结构，恰恰相反，在处理稠密图、需要频繁判断顶点间关系，或者图规模可控的场景下，它清晰、直观且高效的特性，能让你事半功倍。今天，我们就抛开枯燥的理论，直接上手代码，看看如何用邻接矩阵这把“瑞士军刀”，干净利落地解决有向图和有权图的存储与遍历问题。

1. 邻接矩阵：从概念到代码的基石

在深入有向图和有权图之前，我们必须先打好邻接矩阵的基础。你可以把它想象成一个城市的地铁线路图，但我们的“地图”是一个正方形的表格（矩阵），行和列都代表图中的顶点。如果顶点i到顶点j有一条边，我们就在表格的第i行第j列做个标记。对于最简单的无向无权图，这个标记通常就是1（有连接）或0（无连接）。

为什么初学者容易在这里栽跟头？一个常见的误区是混淆了矩阵的“行”与“列”所代表的方向。记住一个核心口诀：行出列入。第i行记录的是从顶点i出发的边（出边），第j列记录的是指向顶点j的边（入边）。这个概念对有向图至关重要。

让我们用Python先搭建一个最基础的邻接矩阵类，感受一下它的骨架：

class AdjacencyMatrix: def __init__(self, num_vertices): """ 初始化一个大小为 num_vertices x num_vertices 的矩阵。 默认所有顶点间没有连接。 """ self.num_vertices = num_vertices # 使用列表推导式创建二维矩阵，所有元素初始化为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: print(f"错误：顶点索引 {u} 或 {v} 超出范围。") def display(self): """以易读格式打印矩阵""" for row in self.matrix: print(' '.join(map(str, row)))

注意：在初始化二维列表时，务必使用[[0] * n for _ in range(n)]，而不是[[0] * n] * n。后者会导致内部列表是同一个对象的引用，修改一行会影响到所有行，这是Python中一个经典的陷阱。

这个基础版本虽然简单，但已经包含了邻接矩阵的核心：一个用0和1填满的二维表格。你可以通过add_edge(0, 1)来建立顶点0和1的连接，然后通过matrix[0][1]的值（1）瞬间判断出它们是否相连。这种常数时间复杂度（O(1)）的查询效率，是邻接矩阵在处理稠密图时最大的优势之一。

2. 有向图的矩阵表示：捕捉箭头的方向

当图中的边有了方向，就像社交网络中的“关注”关系（我关注你，但你未必关注我），邻接矩阵的表示就需要做出关键调整。此时，矩阵不再对称。matrix[i][j] = 1仅表示存在一条从顶点i指向顶点j的弧，反之则不一定成立。

理解有向图邻接矩阵的行和列含义，是掌握其用法的钥匙。我们通过一个具体的微博粉丝关系例子来看：

假设有4个用户：V0（张三）、V1（李四）、V2（王五）、V3（赵六）。关注关系如下：

• 张三关注了李四和王五。
• 李四只关注了赵六。
• 王五关注了张三和赵六。
• 赵六没有关注任何人。

对应的邻接矩阵如下所示（行索引i代表关注者，列索引j代表被关注者）：

从这个表格我们可以直接读出许多信息：

• 求某个用户的出度（他关注了多少人）：查看其所在行的元素之和。例如，张三（V0）所在行的和为 0+1+1+0 = 2，所以他关注了2人。
• 求某个用户的入度（有多少人关注他）：查看其所在列的元素之和。例如，赵六（V3）所在列的和为 0+1+1+0 = 2，所以她有2个粉丝。
• 快速判断关注关系：matrix[2][0] = 1立刻告诉我们，王五（V2）关注了张三（V0）。

基于这个逻辑，我们扩展之前的类，加入有向图的支持：

class DirectedAdjacencyMatrix(AdjacencyMatrix): def add_directed_edge(self, source, target): """ 添加一条从源顶点（source）指向目标顶点（target）的有向边。 """ if 0 <= source < self.num_vertices and 0 <= target < self.num_vertices: self.matrix[source][target] = 1 else: print(f"错误：顶点索引 {source} 或 {target} 超出范围。") def out_degree(self, vertex): """计算指定顶点的出度""" if 0 <= vertex < self.num_vertices: return sum(self.matrix[vertex]) # 对行求和 return -1 def in_degree(self, vertex): """计算指定顶点的入度""" if 0 <= vertex < self.num_vertices: # 对列求和，需要遍历每一行的该列元素 return sum(row[vertex] for row in self.matrix) return -1

在实际项目中，比如构建任务调度系统的依赖图（任务A必须在任务B之前完成），这种有向的邻接矩阵能清晰地表示依赖关系，并且能高效地检测环（例如通过后续要讲的DFS），避免循环依赖导致的死锁。

3. 有权图（网络）的矩阵升级：从“是否”到“多少”

现实世界中的图，边往往带有权重。比如城市交通图中道路的长度、通信网络中链路的带宽、知识图谱中实体关系的强度。这时，我们的矩阵就不能只用0和1了，而需要存储具体的权值。通常，我们用0或一个特定的值（如float('inf')表示无穷大）来表示“没有边”。

我们将矩阵升级为有权图版本。这里的关键决策是：如何表示“无边”？我推荐使用None或一个明确的极大值，这取决于你的算法需求。如果后续要运行最短路径算法（如Floyd-Warshall），使用inf（无穷大）会更方便。

class WeightedAdjacencyMatrix: def __init__(self, num_vertices, no_edge_value=float('inf')): """ 初始化有权图的邻接矩阵。 :param no_edge_value: 用于表示“无边”的值，默认为无穷大。 """ self.num_vertices = num_vertices self.no_edge = no_edge_value self.matrix = [[no_edge_value] * num_vertices for _ in range(num_vertices)] # 顶点到自身的距离通常设为0 for i in range(num_vertices): self.matrix[i][i] = 0 def add_weighted_edge(self, u, v, weight, directed=False): """ 添加一条带权重的边。 :param u: 起始顶点 :param v: 目标顶点 :param weight: 边权重 :param directed: 是否为有向边，默认为无向 """ if 0 <= u < self.num_vertices and 0 <= v < self.num_vertices: self.matrix[u][v] = weight if not directed: self.matrix[v][u] = weight # 无向图，权重对称 else: print(f"错误：顶点索引 {u} 或 {v} 超出范围。") def display(self): """打印矩阵，将无穷大显示为'∞'以便阅读""" for row in self.matrix: display_row = ['∞' if x == float('inf') else str(x) for x in row] print(' '.join(display_row))

假设我们为一个有4个节点的通信网络建模，边的权重代表延迟（毫秒）：

• 节点0到节点1：延迟 10ms
• 节点0到节点2：延迟 5ms
• 节点1到节点3：延迟 2ms
• 节点2到节点3：延迟 8ms
• 其他节点间无直接连接。

构建的矩阵如下：

0 10 5 ∞ 10 0 ∞ 2 5 ∞ 0 8 ∞ 2 8 0

这个矩阵立刻成为了一个强大的数据源。你可以一眼看出任意两个节点间的直接通信延迟，也为后续进行最短路径计算、网络可靠性分析打下了基础。

4. 遍历算法实战：DFS与BFS的矩阵实现

存储好了图，下一步就是探索它。深度优先搜索（DFS）和广度优先搜索（BFS）是两种最基础的图遍历算法，它们的思想同样适用于邻接矩阵。实现的关键在于：如何从矩阵中找到一个顶点的所有邻居？

对于顶点v，我们需要扫描矩阵的第v行（对于有向图是出边邻居）或同时结合行与列（对于无向图），找出所有值不为0（或不为no_edge_value）的列索引，这些索引就是v的邻居顶点。

4.1 深度优先搜索（DFS）实现

DFS像是一个执着于走到底的探险家，使用栈（递归隐式使用调用栈）来探索路径。以下是基于递归的DFS实现，它特别适合邻接矩阵，因为查找邻居的操作很直接。

def dfs_matrix(matrix, start_vertex, visited=None): """ 使用邻接矩阵进行深度优先搜索。 :param matrix: 邻接矩阵（二维列表） :param start_vertex: 起始顶点索引 :param visited: 记录已访问顶点的集合 :return: 深度优先遍历的顺序列表 """ if visited is None: visited = set() order = [] def _dfs(v): visited.add(v) order.append(v) # 记录访问顺序 # 遍历矩阵的第v行，找到所有邻居 for neighbor, is_connected in enumerate(matrix[v]): # 判断是否有边：对于无权图，检查是否为1；对于有权图，检查是否不是无穷大且不等于0（除非是自环） if is_connected != 0 and is_connected != float('inf') and neighbor not in visited: _dfs(neighbor) _dfs(start_vertex) return order # 使用示例 # 假设我们有一个前面定义的无向图邻接矩阵实例 `graph` # traversal_order = dfs_matrix(graph.matrix, 0) # print("DFS遍历顺序:", traversal_order)

提示：对于非常大的图，递归DFS可能导致栈溢出。在这种情况下，可以显式使用栈数据结构来实现迭代版本的DFS，逻辑相同，只是将递归调用改为入栈操作。

4.2 广度优先搜索（BFS）实现

BFS则像水波扩散，一层一层地探索，使用队列来保证顺序。它在寻找最短路径（在边权为1的情况下）或层次遍历时非常有用。

from collections import deque def bfs_matrix(matrix, start_vertex): """ 使用邻接矩阵进行广度优先搜索。 :param matrix: 邻接矩阵 :param start_vertex: 起始顶点索引 :return: 广度优先遍历的顺序列表 """ visited = set([start_vertex]) queue = deque([start_vertex]) order = [] while queue: vertex = queue.popleft() order.append(vertex) # 查找当前顶点的所有未访问邻居 for neighbor, is_connected in enumerate(matrix[vertex]): if is_connected != 0 and is_connected != float('inf') and neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return order

为了更直观地对比这两种遍历策略，我们用一个简单的5顶点图来演示：

假设矩阵表示的图连接如下：0-1, 0-2, 1-3, 2-4。 从顶点0开始遍历：

• DFS顺序可能是 [0, 1, 3, 2, 4]（如果先探索邻居1）或 [0, 2, 4, 1, 3]（如果先探索邻居2），它倾向于深入一条分支。
• BFS顺序一定是 [0, 1, 2, 3, 4]，它严格按照距离起始点的层次来访问。

选择DFS还是BFS，取决于你的需求。如果你想检查图的连通性、找环或进行拓扑排序，DFS是更自然的选择。如果你需要找最少步数的路径或进行层级分析，BFS则是利器。

5. 避坑指南与性能优化实战

邻接矩阵看似简单，但实践中仍有不少陷阱。我结合自己踩过的坑，分享几个关键点。

常见陷阱1：索引越界与初始化错误这是最典型的错误。始终记住，顶点索引应从0到n-1。在add_edge方法中，首要操作就是进行边界检查。初始化矩阵时，如前所述，避免使用[[0]*n]*n这种写法。

常见陷阱2：有向与无向的混淆在实现通用图类时，最好用一个布尔标志directed来明确图的类型。添加边时，根据这个标志决定是否设置对称元素。

def add_edge(self, u, v, weight=1, directed=False): # ... 边界检查 self.matrix[u][v] = weight if not directed and u != v: # 无向图且不是自环 self.matrix[v][u] = weight

性能考量与优化邻接矩阵的优缺点非常分明：

• 优点：
  • 查询边是否存在：O(1)，极快。
  • 添加/删除边：O(1)。
  • 适合稠密图（边数接近顶点数的平方）。
  • 实现简单，易于理解。
• 缺点：
  • 空间复杂度高：O(V²)，对于顶点数多但边数少的稀疏图极其浪费空间。
  • 查找一个顶点的所有邻居：O(V)，即使它只有几个邻居，也需要扫描整行。

注意：当图非常稀疏时（例如社交网络，每个人只连接少量朋友），邻接表通常是更优的选择。但在图规模不大（比如顶点数小于1000），或需要频繁进行边存在性检查的算法中（如传递闭包、某些动态规划算法），邻接矩阵的优势无法替代。

一个实用的优化技巧：使用NumPy如果使用Python且对性能有要求，强烈建议用NumPy数组替代二维列表。它在存储和数值计算上效率高得多。

import numpy as np class NumpyAdjacencyMatrix: def __init__(self, num_vertices): self.matrix = np.zeros((num_vertices, num_vertices), dtype=int) # ... 其他方法可以基于NumPy的向量化操作，速度更快

最后，调试邻接矩阵驱动的图算法时，一个直观的可视化方法胜过千言万语。可以写一个简单的函数将矩阵打印成带边框的表格，或者生成Graphviz的DOT语言代码来渲染图像，这能帮你快速验证图的结构是否正确。例如，在实现DFS后，如果遍历顺序不符合预期，第一件事就是打印出邻接矩阵，检查边的设置是否与你设想的一致。很多时候，bug就藏在那几个0和1之间。