亚灿网志 - NetworkX
type: channel
link: https://blog.manyacan.com/tag/NetworkX/
items: 「图论入门」从基础概念到NetworkX

「图论入门」从基础概念到NetworkX
type: item
date: 2023-12-12T12:42:00+08:00
description: 介绍图（Graph）是一种表示对象之间关系的抽象数据结构。图由节点（Vertex）和边（Edge）组成，节点表示对象，边表示对象之间的关系。图可以用于建模各种实际问题，如社交网络、交通网络、电力网络等。NetworkX是一个用Python编写的库，专门用于创建、操作和研究复杂网络的结构、动态和功能。它提供了简单易用的接口来处理图论和网络结构。NetworkX适用于处理大型网络结构，并提供了许多内置的图算法，如路径寻找、图的构建和修改、节点属性操作等。NetworkX官方文档（网站）：https://networkx.org/；使用pip安装：pip install networkx并回车。基本概念无向图（Undirected Graph）import networkx as nx # 创建一个无向图 G = nx.Graph() # 添加节点 G.add_node(1) G.add_nodes_from([2, 3]) # 添加边 G.add_edge(1, 2) G.add_edges_from([(2, 3), (1, 3)]) # 查看图的节点和边 print("图的节点: ", G.nodes(), "; 图的边: ", G.edges(), '.') # 可视化 nx.draw(G, node_size=500, with_labels=True)控制台输出结果 - 无向图有向图（Directed Graph）有向图的创建方式很简单，只需要把上面无向图的对象：# 创建一个无向图 G = nx.Graph()换成：# 创建一个有向图 G = nx.DiGraph()即可。控制台输出结果 - 有向图有权图（Directed Graph）创建有权图时需要添加权重信息，且可视化的代码略有不同：import networkx as nx import matplotlib.pyplot as plt # 创建一个带权重的无向图 G = nx.Graph() # 添加带权重的边 G.add_edges_from([ (2, 3, {'diameter': 1.0,'length': 12.0}), (1, 3, {'diameter': 2.0,'length': 10.0}), (2, 1, {'diameter': 3.0,'length': 8.0}) ]) # 提取权重信息 edge_weights = nx.get_edge_attributes(G, 'length') # 可视化图 pos = nx.spring_layout(G) # 选择布局算法，这里使用弹簧布局 nx.draw(G, pos, with_labels=True, font_weight='bold', node_size=700, node_color='skyblue', font_color='black') # 绘制权重标签 nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_weights) # 显示图形 plt.show() # 查看图的节点和边 print("图的节点: ", G.nodes(), "; 图的边: ", G.edges(data=True), '.')控制台输出结果 - 有权图邻接矩阵邻接矩阵（Adjacency Matrix）： 邻接矩阵是一个二维矩阵，其中的行和列分别对应图中的节点。矩阵的元素表示节点之间是否存在边。对于无向图，邻接矩阵是对称的；对于有向图，邻接矩阵不一定对称。# 获取邻接矩阵(默认是稀疏矩阵格式) adj_matrix = nx.adjacency_matrix(G) # 将稀疏矩阵转换为密集矩阵(如果需要) dense_adj_matrix = adj_matrix.todense()请注意，如果你的图是有向图，你可以使用 nx.adjacency_matrix(G, directed=True) 来获取有向图的邻接矩阵。如果你想要自定义矩阵的表示方式，你可以使用 toarray() 方法将稀疏矩阵转换为 NumPy 数组。关联矩阵在 networkx 库中，nx.incidence_matrix(G) 用于生成图 G 的关联矩阵（Incidence Matrix）。关联矩阵和邻接矩阵不同，它是一种表示图中节点与边之间关系的矩阵。对于一个包含 $ N $ 个节点和 $ M $ 条边的图，其关联矩阵是一个 $ N \times M $ 的矩阵，其中矩阵的行对应图中的节点，列对应图中的边。关联矩阵中的元素定义如下：如果边 $ e $ 与节点 $ v $ 相连，则矩阵中对应位置的值为 1（或者对于有向图，出边为 -1，入边为 1）；如果边 $…