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 sympy

import sympy as sym

2.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^T（B为关联矩阵）可以得到一个与图结构相关的矩阵：

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算法通常比矩阵表示更高效。