# 离散数学图论入门：邻接矩阵与关联矩阵的Python实现（Educoder实训指南） 图论作为离散数学的核心分支，在计算机科学、网络分析、社交关系建模等领域具有广泛应用。本文将深入浅出地介绍图的两种基础表示方法——邻接矩阵与关联矩阵，并通过Python代码实现这些数据结构，帮助读者在Educoder等实训平台上快速掌握图论的核心概念与编程技巧。 ## 1. 图的基本概念与表示方法 图（Graph）是由顶点集合V和边集合E组成的数学结构，记作G=(V,E)。根据边的方向性，图可分为有向图和无向图；根据边是否带有权重，又可分为无权图和加权图。理解这些基础分类是掌握图论的第一步。 图的表示方法直接影响算法的效率与实现难度。最常见的两种表示方式是： - **邻接矩阵（Adjacency Matrix）**：用二维数组表示顶点间的连接关系 - **关联矩阵（Incidence Matrix）**：用矩阵表示顶点与边的关联关系 下面通过一个简单示例说明两者的区别。假设有如下无向图： ``` v1 —— v2 | \ / | \ / v3 —— v4 ``` ### 1.1 邻接矩阵原理与特点 邻接矩阵是一个n×n的方阵（n为顶点数），其中元素a[i][j]表示顶点i与j之间的连接情况： - 无权图中：1表示连接，0表示无连接 - 加权图中：存储边的权重值 - 无向图的邻接矩阵是对称的 上述示例图的邻接矩阵表示为： ```python [ [0, 1, 1, 1], # v1连接v2,v3,v4 [1, 0, 0, 1], # v2连接v1,v4 [1, 0, 0, 1], # v3连接v1,v4 [1, 1, 1, 0] # v4连接v1,v2,v3 ] ``` 邻接矩阵的优势在于： - 快速判断任意两顶点是否相邻（O(1)时间复杂度） - 方便计算顶点的度（行或列非零元素个数） ### 1.2 关联矩阵原理与应用场景 关联矩阵是一个n×m的矩阵（n为顶点数，m为边数），其中： - 行代表顶点 - 列代表边 - 元素值表示顶点与边的关联关系 对于同一个示例图，其关联矩阵可能表示为： ```python [ [1, 1, 1, 0], # v1关联边e1,e2,e3 [1, 0, 0, 1], # v2关联边e1,e4 [0, 1, 0, 1], # v3关联边e2,e4 [0, 0, 1, 1] # v4关联边e3,e4 ] ``` 关联矩阵特别适合处理： - 多重图（存在多条相同顶点间的边） - 超图（一条边可以连接多个顶点） - 网络流问题中的边操作 ## 2. Python实现图的矩阵表示 在实际编程中，我们可以使用Python的NumPy或SymPy库高效实现矩阵运算。下面以Educoder实训平台常见的题目为例，演示具体实现方法。 ### 2.1 使用SymPy构建邻接矩阵 SymPy是Python的符号计算库，适合处理数学表达式和矩阵运算。以下是创建邻接矩阵的完整示例： ```python import sympy as sym # 定义图的顶点和边 vertices = ['v1', 'v2', 'v3', 'v4'] edges = [('v1','v2'), ('v1','v3'), ('v1','v4'), ('v2','v4'), ('v3','v4')] # 初始化邻接矩阵 n = len(vertices) adj_matrix = sym.zeros(n, n) # 填充邻接矩阵 vertex_index = {v:i for i,v in enumerate(vertices)} for u, v in edges: i, j = vertex_index[u], vertex_index[v] adj_matrix[i,j] = 1 adj_matrix[j,i] = 1 # 无向图需对称赋值 print("邻接矩阵：") sym.pprint(adj_matrix) ``` ### 2.2 关联矩阵的Python实现 关联矩阵的实现需要考虑边的编号和顶点关联关系： ```python # 继续使用前面的vertices和edges m = len(edges) inc_matrix = sym.zeros(n, m) # 填充关联矩阵 for edge_idx, (u, v) in enumerate(edges): i, j = vertex_index[u], vertex_index[v] inc_matrix[i, edge_idx] = 1 inc_matrix[j, edge_idx] = 1 print("\n关联矩阵：") sym.pprint(inc_matrix) ``` ### 2.3 矩阵表示的性能对比 | 表示方法 | 空间复杂度 | 查询相邻顶点 | 查询边信息 | 添加顶点 | 添加边 | |----------|------------|--------------|------------|----------|--------| | 邻接矩阵 | O(V²) | O(1) | O(1) | O(V²) | O(1) | | 关联矩阵 | O(V×E) | O(E) | O(V) | O(E) | O(V) | > 提示：对于稀疏图（边数远小于顶点数平方），邻接表（Adjacency List）通常是更高效的表示方法，但不在本文讨论范围内。 ## 3. 图论算法实战：Dijkstra最短路径 理解了图的表示方法后，我们可以实现经典的Dijkstra算法，解决单源最短路径问题。该算法要求图中不存在负权边。 ### 3.1 Dijkstra算法原理 算法步骤如下： 1. 初始化：设置起点距离为0，其他顶点距离为∞ 2. 选择当前距离最小的未访问顶点u 3. 对u的每个邻接顶点v，更新其距离值 4. 标记u为已访问 5. 重复步骤2-4，直到所有顶点都被访问 ### 3.2 基于邻接矩阵的Python实现 ```python import heapq def dijkstra(adj_matrix, start): n = len(adj_matrix) dist = [float('inf')] * n dist[start] = 0 visited = set() heap = [(0, start)] while heap: current_dist, u = heapq.heappop(heap) if u in visited: continue visited.add(u) for v in range(n): if adj_matrix[u][v] > 0: # 存在边 new_dist = current_dist + adj_matrix[u][v] if new_dist < dist[v]: dist[v] = new_dist heapq.heappush(heap, (new_dist, v)) return dist # 示例：带权邻接矩阵 weighted_adj = [ [0, 2, 6, 3], [2, 0, 0, 1], [6, 0, 0, 2], [3, 1, 2, 0] ] print("最短距离：", dijkstra(weighted_adj, 0)) ``` ### 3.3 Educoder实训常见问题解析 在Educoder平台完成图论实训时，需要注意以下常见问题： 1. **矩阵索引问题**：Python使用0-based索引，而题目描述可能使用1-based 2. **无向图对称性**：构建邻接矩阵时不要忘记对称赋值 3. **Dijkstra算法实现**： - 正确初始化距离数组 - 使用优先队列提高效率 - 处理不可达顶点（保持∞或设为特定值） ## 4. 进阶应用与性能优化 掌握了基础实现后，我们可以进一步优化代码并扩展应用场景。 ### 4.1 稀疏图的优化处理 对于大型稀疏图，邻接矩阵会浪费大量空间。可以使用稀疏矩阵表示： ```python from scipy.sparse import lil_matrix # 创建稀疏邻接矩阵 sparse_adj = lil_matrix((n, n), dtype=int) for u, v in edges: i, j = vertex_index[u], vertex_index[v] sparse_adj[i,j] = 1 sparse_adj[j,i] = 1 ``` ### 4.2 可视化图结构 使用networkx和matplotlib可以直观展示图结构： ```python import networkx as nx import matplotlib.pyplot as plt G = nx.Graph() G.add_nodes_from(vertices) G.add_edges_from(edges) nx.draw(G, with_labels=True, node_color='lightblue') plt.show() ``` ### 4.3 实际应用案例 图论在现实世界中有广泛应用，例如： - **社交网络分析**：使用邻接矩阵表示用户关系 - **交通路径规划**：Dijkstra算法计算最短行驶路线 - **推荐系统**：基于图结构进行商品或内容推荐 在Educoder实训中，建议从简单图入手，逐步增加复杂度。例如先实现无向无权图，再扩展到有向加权图；先完成静态图操作，再尝试动态图算法。