Python sympy 实战5分钟构建图论关联矩阵与邻接矩阵附头歌实训代码当你在学习离散数学或图论时是否曾被那些抽象的图形和复杂的关系所困扰今天我将带你用Python的sympy库在短短5分钟内实现图论的两种核心矩阵表示——关联矩阵和邻接矩阵。这不仅能让抽象概念变得可视化还能通过代码加深你对图论本质的理解。1. 图论矩阵表示的基础概念在开始编码之前我们需要明确几个基本概念。图论中的图由**顶点(Vertex)和边(Edge)**组成而矩阵表示则是将这些点和线的关系数字化的重要方式。**邻接矩阵(Adjacency Matrix)**记录的是顶点之间的直接连接关系。对于一个有n个顶点的图邻接矩阵是一个n×n的方阵其中元素a_ij表示顶点i和顶点j之间是否存在边。# 一个简单无向图的邻接矩阵示例 # 顶点0连接顶点1和顶点2 adj_matrix [ [0, 1, 1], [1, 0, 0], [1, 0, 0] ]**关联矩阵(Incidence Matrix)**则记录的是顶点与边的关系。对于一个有n个顶点和m条边的图关联矩阵是一个n×m的矩阵其中元素b_ij表示顶点i是否与边j相关联。两种矩阵各有优势邻接矩阵更擅长表示顶点间的直接连接关联矩阵更适合表示边与顶点的对应关系提示在实际应用中邻接矩阵更适合稠密图而关联矩阵在处理多图同一对顶点间有多条边时更有优势。2. 使用sympy构建矩阵表示sympy是Python的一个符号计算库它提供了强大的矩阵操作功能特别适合用于数学概念的编程实现。下面我们来看如何用sympy构建这两种矩阵。首先安装并导入必要的库pip install sympyimport sympy as sym2.1 从边列表生成邻接矩阵假设我们有一个图的边列表表示每条边是一个顶点对edges [(0, 1), (0, 2), (1, 2), (2, 3)] num_vertices 4构建邻接矩阵的函数如下def build_adjacency_matrix(edges, num_vertices): # 初始化全零矩阵 adj sym.zeros(num_vertices, num_vertices) for u, v in edges: # 无向图所以两个方向都要设置 adj[u, v] 1 adj[v, u] 1 return adj测试这个函数adj_matrix build_adjacency_matrix(edges, num_vertices) print(邻接矩阵:) sym.pprint(adj_matrix)输出结果⎡0 1 1 0⎤ ⎢ ⎥ ⎢1 0 1 0⎥ ⎢ ⎥ ⎢1 1 0 1⎥ ⎢ ⎥ ⎣0 0 1 0⎦2.2 从边列表生成关联矩阵构建关联矩阵需要为每条边分配一个唯一的标识。我们可以简单地将边列表的索引作为边的ID。def build_incidence_matrix(edges, num_vertices): num_edges len(edges) inc sym.zeros(num_vertices, num_edges) for edge_idx, (u, v) in enumerate(edges): inc[u, edge_idx] 1 inc[v, edge_idx] 1 return inc测试关联矩阵生成inc_matrix build_incidence_matrix(edges, num_vertices) print(关联矩阵:) sym.pprint(inc_matrix)输出结果⎡1 1 0 0⎤ ⎢ ⎥ ⎢1 0 1 0⎥ ⎢ ⎥ ⎢0 1 1 1⎥ ⎢ ⎥ ⎣0 0 0 1⎦3. 矩阵表示的实际应用对比不同的矩阵表示适用于不同的场景。下面我们通过一个对比表格来理解它们的差异特性邻接矩阵关联矩阵矩阵维度n×n (n为顶点数)n×m (m为边数)存储空间O(n²)O(n×m)查找两顶点是否相邻O(1)O(m)查找顶点的所有邻居O(n)O(m)表示带权图直接用权重代替1需要扩展表示方法表示有向图非对称矩阵用1/-1表示方向适用场景稠密图频繁查询顶点连接稀疏图需要处理边属性的场景在实际的头歌实训项目中这两种表示方法都会被用到。例如在图的表示这一关中你需要同时实现两种矩阵表示而在单源最短通路问题中邻接矩阵或邻接表的表示更为常用。4. 头歌实训代码实战解析让我们结合头歌实训平台的具体要求实现一个完整的解决方案。实训通常要求从给定的边列表生成两种矩阵表示并进行一些基本的图论计算。4.1 完整解决方案代码import sympy as sym def graph_representation(edges, num_vertices): 根据边列表生成邻接矩阵和关联矩阵 参数: edges: 边列表每个元素是顶点对元组 num_vertices: 图中顶点的总数 返回: (adj_matrix, inc_matrix) 邻接矩阵和关联矩阵的元组 # 初始化邻接矩阵 adj sym.zeros(num_vertices, num_vertices) # 初始化关联矩阵 inc sym.zeros(num_vertices, len(edges)) for edge_idx, (u, v) in enumerate(edges): # 构建邻接矩阵 adj[u, v] 1 adj[v, u] 1 # 构建关联矩阵 inc[u, edge_idx] 1 inc[v, edge_idx] 1 return adj, inc # 示例使用 if __name__ __main__: # 示例图4个顶点4条边 edges [(0, 1), (0, 2), (1, 2), (2, 3)] num_vertices 4 adj, inc graph_representation(edges, num_vertices) print(邻接矩阵:) sym.pprint(adj) print(\n关联矩阵:) sym.pprint(inc)4.2 代码优化与错误处理在实际的头歌实训提交中我们还需要考虑一些边界情况和平台的特殊要求def graph_representation_enhanced(edges, num_vertices): 增强版的图表示函数处理更多边界情况 if not edges or num_vertices 0: return sym.zeros(1, 1), sym.zeros(1, 1) # 返回空矩阵 try: # 检查边是否合法 for u, v in edges: if u num_vertices or v num_vertices or u 0 or v 0: raise ValueError(顶点索引超出范围) # 构建矩阵 adj sym.zeros(num_vertices, num_vertices) inc sym.zeros(num_vertices, len(edges)) for edge_idx, (u, v) in enumerate(edges): adj[u, v] 1 adj[v, u] 1 inc[u, edge_idx] 1 inc[v, edge_idx] 1 return adj, inc except Exception as e: print(f错误: {e}) return sym.zeros(1, 1), sym.zeros(1, 1)注意头歌实训平台通常会提供特定的输入输出格式要求务必仔细阅读题目说明调整打印输出的格式。5. 进阶应用矩阵运算在图论中的应用掌握了矩阵表示后我们可以利用矩阵运算来解决一些图论问题。例如邻接矩阵的幂可以告诉我们顶点之间通过一定步数的路径数量。5.1 计算路径数量邻接矩阵A的k次幂A^k中的元素a_ij^(k)表示从顶点i到顶点j长度为k的路径数量。def count_paths(adj_matrix, k): 计算所有顶点之间长度为k的路径数量 return adj_matrix ** k # 示例计算长度为2的路径 adj_matrix build_adjacency_matrix([(0,1),(1,2),(2,3)], 4) paths_2 count_paths(adj_matrix, 2) print(长度为2的路径数量矩阵:) sym.pprint(paths_2)5.2 判断图的连通性通过邻接矩阵的幂运算我们可以判断图是否连通def is_connected(adj_matrix): 判断图是否连通 n adj_matrix.rows total sum(adj_matrix ** k for k in range(1, n)) return all(total[i, j] 0 for i in range(n) for j in range(n) if i ! j) # 示例使用 edges_connected [(0,1),(1,2),(2,3)] edges_disconnected [(0,1),(2,3)] adj_connected build_adjacency_matrix(edges_connected, 4) adj_disconnected build_adjacency_matrix(edges_disconnected, 4) print(图1是否连通:, is_connected(adj_connected)) print(图2是否连通:, is_connected(adj_disconnected))5.3 关联矩阵的转置应用关联矩阵的转置也有其特殊意义。B×B^TB为关联矩阵可以得到一个与图结构相关的矩阵def incidence_transpose_application(inc_matrix): 关联矩阵转置的应用示例 return inc_matrix * inc_matrix.T # 示例使用 edges [(0,1),(0,2),(1,2)] inc build_incidence_matrix(edges, 3) result incidence_transpose_application(inc) print(B×B^T的结果:) sym.pprint(result)在实际项目中我发现矩阵运算虽然强大但对于大规模图可能会遇到性能问题。这时可以考虑使用稀疏矩阵表示或优化算法。例如在头歌实训的单源最短通路问题中使用邻接表结合优先队列的Dijkstra算法通常比矩阵表示更高效。