Python sympy 1.12 实战：5分钟构建图论关联与邻接矩阵（附头歌实训题解）
当你第一次接触图论时，那些抽象的点和线可能会让你感到困惑。但作为一名计算机专业的学生，我清楚地记得自己是如何通过Python的sympy库，将这些抽象概念转化为具体的矩阵表示，从而真正理解了图论的本质。本文将带你快速掌握这一实用技能，并解决头歌实训中的实际编程问题。
1. 图论基础与矩阵表示
图论作为离散数学的重要分支，研究的是由顶点（vertex）和边（edge）组成的图结构。在实际应用中，我们需要将这些抽象的结构转化为计算机能够处理的数据形式——这就是矩阵表示法的价值所在。
邻接矩阵（Adjacency Matrix）和关联矩阵（Incidence Matrix）是两种最常用的图表示方法：
- 邻接矩阵：表示顶点之间的连接关系
- 关联矩阵：表示顶点与边之间的关联关系
在Python中，我们可以使用sympy库的Matrix类来优雅地实现这些矩阵表示。下面是一个简单的无向图示例：
import sympy as sym # 定义无向图的邻接矩阵 adj_matrix = sym.Matrix([ [0, 1, 0, 1], [1, 0, 1, 1], [0, 1, 0, 1], [1, 1, 1, 0] ])这个4×4的矩阵表示一个有4个顶点的图，其中1表示顶点之间有边相连，0表示没有连接。
2. sympy.Matrix的图论应用
sympy库的Matrix类为图论矩阵操作提供了强大的支持。相比原生Python列表或numpy数组，sympy.Matrix有以下优势：
- 符号计算能力
- 内置的矩阵运算方法
- 美观的打印输出格式
创建关联矩阵的通用模板：
def create_incidence_matrix(vertices, edges): """ 创建图的关联矩阵 参数： vertices: 顶点数量 edges: 边列表，每个边表示为(起点, 终点) 返回： sympy.Matrix对象 """ matrix = [] for edge in edges: row = [0] * vertices row[edge[0]] = 1 # 起点 row[edge[1]] = 1 # 终点 matrix.append(row) return sym.Matrix(matrix)使用这个模板，我们可以轻松地为任何图创建关联矩阵。例如，处理头歌实训中的图1：
# 图1的边定义 edges = [(0,1), (0,3), (1,2), (1,3), (2,3)] # 创建关联矩阵 A1 = create_incidence_matrix(4, edges) print(A1)3. 头歌实训第2关完整解决方案
头歌实训的第2关要求我们为给定的图创建关联矩阵和邻接矩阵。下面是一个完整的、可直接运行的解决方案：
#coding=utf-8 import sympy as sym def solve_educoder_case(): # 关联矩阵A1表示图1 A1 = sym.Matrix([ [1, 0, 0, 1, 0], [1, 1, 0, 0, 1], [0, 1, 1, 0, 0], [0, 0, 1, 1, 1] ]) # 邻接矩阵B1表示图1 B1 = sym.Matrix([ [0, 1, 0, 1], [1, 0, 1, 1], [0, 1, 0, 1], [1, 1, 1, 0] ]) # 输出结果 print("关联矩阵A1:") sym.pprint(A1) print("\n邻接矩阵B1:") sym.pprint(B1) # 判断两个图是否相同（通过邻接矩阵比较） A2 = A1.copy() B2 = B1.copy() if B1 == B2: print("\n两个图相同") else: print("\n两个图不同") solve_educoder_case()这段代码不仅满足了实训要求，还增加了以下改进：
- 使用sympy的pprint函数实现美观输出
- 添加了清晰的注释说明
- 封装为函数，提高代码复用性
4. 矩阵与图结构的对应关系解析
理解矩阵元素与图结构之间的对应关系是掌握图论的关键。让我们通过一个表格来清晰地展示这种对应关系：
| 矩阵类型 | 矩阵元素a[i][j]的含义 | 示例解释 |
|---|---|---|
| 邻接矩阵 | 顶点i与顶点j之间是否有边相连 | a[1][2]=1表示顶点1和2之间有边 |
| 关联矩阵 | 顶点i是否与边j相关联 | a[0][3]=1表示顶点0与边3相连 |
邻接矩阵的特点：
- 对于无向图，矩阵是对称的
- 对角线元素通常为0（除非有自环）
- 行/列和表示顶点的度数
关联矩阵的特点：
- 每列恰好有两个1（一条边连接两个顶点）
- 行和表示顶点的度数
- 列和总是2
通过这种对应关系，我们可以在矩阵运算和图结构操作之间自由转换，这是解决许多图论问题的基础。
5. 进阶应用：从矩阵到图算法
掌握了矩阵表示后，我们可以进一步实现各种图算法。以Dijkstra最短路径算法为例，邻接矩阵是其自然的输入形式。以下是基于邻接矩阵的实现：
def dijkstra(adj_matrix, start): n = adj_matrix.rows # 顶点数量 INF = float('inf') # 初始化距离和前驱节点 dist = [INF] * n dist[start] = 0 prev = [-1] * n visited = [False] * n for _ in range(n): # 找到未访问的最小距离顶点 u = min((v for v in range(n) if not visited[v]), key=lambda v: dist[v]) visited[u] = True # 更新邻接顶点的距离 for v in range(n): if adj_matrix[u,v] > 0 and not visited[v]: new_dist = dist[u] + adj_matrix[u,v] if new_dist < dist[v]: dist[v] = new_dist prev[v] = u return dist, prev # 示例使用 adj_matrix = sym.Matrix([ [0, 6, 1, 0, 0, 4, 2], [6, 0, 5, 10, 0, 0, 9], [1, 5, 0, 0, 0, 0, 0], [0, 10, 0, 0, 8, 0, 5], [0, 0, 0, 8, 0, 5, 0], [4, 0, 0, 0, 5, 0, 7], [2, 9, 0, 5, 0, 7, 0] ]) distances, predecessors = dijkstra(adj_matrix, 0) print(f"从顶点0出发的最短距离: {distances}") print(f"前驱节点列表: {predecessors}")这个实现展示了如何将邻接矩阵直接应用于经典图算法。在实际的头歌实训第3关中，你可以根据需要调整输入格式和输出要求。
6. 常见问题与调试技巧
在使用sympy处理图论矩阵时，可能会遇到一些典型问题。以下是我在学习和教学过程中总结的经验：
问题1：矩阵维度不匹配
注意：关联矩阵的行数等于顶点数，列数等于边数；而邻接矩阵是方阵，大小等于顶点数。
问题2：无向图与有向图的混淆
- 无向图的邻接矩阵是对称的
- 有向图的邻接矩阵通常不对称
调试建议：
- 对于小型图，先手工绘制图形和对应的矩阵
- 使用sympy的pprint函数检查矩阵输出
- 验证矩阵的基本性质（如对称性、行和列和）
# 验证邻接矩阵对称性的示例 def is_symmetric(matrix): return matrix == matrix.T # 验证关联矩阵每列和为2的示例 def validate_incidence_matrix(matrix): for col in range(matrix.cols): if sum(matrix[:,col]) != 2: return False return True掌握了这些技巧后，你就能更自信地应对各种图论编程挑战了。
