Python生成邻接矩阵 · 图论基石
在Python生成邻接矩阵的实践中,我们探索图数据结构从理论到代码的转化。邻接矩阵是表示顶点间关系的二维数组,广泛应用于社交网络、路径规划等领域。本站聚焦〈NumPy〉〈NetworkX〉及〈SciPy〉等方案,提供详实示例。
① 列表推导式
使用原生Python列表构建邻接矩阵,适合小型图。例如 [[0,1,0],[1,0,1],[0,1,0]] 表示无向路径。
② NumPy数组
numpy.ndarray 提供高效数值运算,通过np.zeros((n,n))初始化,再按边赋值。
③ NetworkX
nx.adjacency_matrix(G) 直接返回稀疏矩阵,支持Graph、DiGraph等类型。
〈 核心方法解析 〉
▸ 纯Python列表生成邻接矩阵
对于顶点数V=4的有向图,边集合〈(0,1),(1,2),(2,3)〉,可手动构建:
matrix = [[0,1,0,0],
[0,0,1,0],
[0,0,0,1],
[0,0,0,0]]
此方法直观,但大型图效率低。网友常结合列表生成式动态创建:[[0]*n for _ in range(n)]。
▸ NumPy高效矩阵
利用numpy库,可快速生成邻接矩阵并执行线性代数运算。示例:
import numpy as np
n = 5
adj = np.zeros((n, n), dtype=int)
edges = [(0,2), (1,3), (2,4)]
for i,j in edges:
adj[i][j] = 1
NumPy支持矩阵乘法计算路径数量,是图算法基础。
▸ SciPy稀疏矩阵
当图稀疏时,scipy.sparse 模块节省内存。常用lil_matrix或csr_matrix:
from scipy.sparse import lil_matrix adj_sparse = lil_matrix((6,6)) adj_sparse[0,1] = 1
网友还关心如何转为稠密格式:.toarray()。
〈 库与工具对比 〉
※ 许多开发者使用NetworkX构建图后,通过nx.to_numpy_array(G)获得邻接矩阵。
〈 网友们还关心 〉
⚙️ 如何从边列表生成邻接矩阵?
定义顶点数n,初始化零矩阵,遍历边列表〈(u,v)〉设置adj[u][v]=1。对于加权图,存储权重值。
📌 邻接矩阵与邻接表区别
矩阵占用O(V²)空间,适合稠密图;邻接表节省空间。Python中可用dict of list实现邻接表。
◎ 稀疏矩阵存储方案
使用scipy.sparse.csr_matrix,支持快速行切片。通过sparse.csr_matrix((data, (row, col)))构建。
▽ 有向图与无向图
无向图邻接矩阵对称,有向图不一定。生成时需注意边方向。
〈 拓展应用 · 图算法 〉
◤ 度矩阵计算
度矩阵是对角阵,D[i][i]为顶点i的度。可通过np.sum(adj, axis=1)获得。
◢ 拉普拉斯矩阵
L = D - A,在谱聚类中关键。Python生成邻接矩阵后直接相减。
- NetworkX 内置
nx.laplacian_matrix(G) - 使用Python生成邻接矩阵后,可调用scipy.sparse.csgraph进行连通分量分析。
- 图卷积网络(GCN)中,邻接矩阵需归一化:D^{-1/2} A D^{-1/2}。
〖 实践建议 〗 对于大型图,优先使用稀疏邻接矩阵。通过python生成邻接矩阵的多种途径,开发者能灵活应对不同规模的数据结构挑战。记住:邻接矩阵是图计算的核心桥梁。
■ 从CSV文件批量生成邻接矩阵
许多数据集以边列表CSV提供,使用pandas读取后,通过pivot或迭代填充矩阵。示例:df = pd.read_csv('edges.csv'),然后遍历行构建矩阵。对于加权网络,第三列存储权重。
另外,python生成邻接矩阵时需注意索引从0开始。若顶点编号不连续,可使用映射字典〈node→idx〉。
⚡ 性能提示:对于百万级顶点,推荐scipy.sparse或igraph库。网友常搜索“python 大图邻接矩阵内存不足”,解决方案即稀疏格式。