Python sympy 1.12 实战：5分钟构建图论关联与邻接矩阵（附头歌实训题解）

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有以下优势：

1. 符号计算能力
2. 内置的矩阵运算方法
3. 美观的打印输出格式

创建关联矩阵的通用模板：

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()

这段代码不仅满足了实训要求，还增加了以下改进：

1. 使用sympy的pprint函数实现美观输出
2. 添加了清晰的注释说明
3. 封装为函数，提高代码复用性

4. 矩阵与图结构的对应关系解析

理解矩阵元素与图结构之间的对应关系是掌握图论的关键。让我们通过一个表格来清晰地展示这种对应关系：

邻接矩阵的特点：

• 对于无向图，矩阵是对称的
• 对角线元素通常为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：无向图与有向图的混淆

• 无向图的邻接矩阵是对称的
• 有向图的邻接矩阵通常不对称

调试建议：

1. 对于小型图，先手工绘制图形和对应的矩阵
2. 使用sympy的pprint函数检查矩阵输出
3. 验证矩阵的基本性质（如对称性、行和列和）

# 验证邻接矩阵对称性的示例 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

掌握了这些技巧后，你就能更自信地应对各种图论编程挑战了。