邻接矩阵实战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代表被关注者V0V1V2V3V00110V10001V21001V30000从这个表格我们可以直接读出许多信息求某个用户的出度他关注了多少人查看其所在行的元素之和。例如张三V0所在行的和为 0110 2所以他关注了2人。求某个用户的入度有多少人关注他查看其所在列的元素之和。例如赵六V3所在列的和为 0110 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_valuefloat(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, directedFalse): 添加一条带权重的边。 :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, visitedNone): 使用邻接矩阵进行深度优先搜索。 :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, weight1, directedFalse): # ... 边界检查 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), dtypeint) # ... 其他方法可以基于NumPy的向量化操作速度更快最后调试邻接矩阵驱动的图算法时一个直观的可视化方法胜过千言万语。可以写一个简单的函数将矩阵打印成带边框的表格或者生成Graphviz的DOT语言代码来渲染图像这能帮你快速验证图的结构是否正确。例如在实现DFS后如果遍历顺序不符合预期第一件事就是打印出邻接矩阵检查边的设置是否与你设想的一致。很多时候bug就藏在那几个0和1之间。