在 Python 中，图论（Graph Theory）通常通过专门的库来实现，最常用的是 NetworkX 和 igraph，对于大规模图或需要高性能计算的场景，还可以使用 Graph-tool 或结合 NumPy/SciPy 处理稀疏矩阵。
下面我将以 NetworkX 为主，介绍 Python 中图论的基本操作、常用算法和可视化方法。
安装依赖
pip install networkx matplotlib
networkx：用于构建图、运行算法。matplotlib：用于可视化图结构。
基本图操作
创建图
import networkx as nx
import matplotlib.pyplot as plt
# 创建无向图
G = nx.Graph()
# 添加节点
G.add_node(1)
G.add_nodes_from([2, 3, 4])
# 添加边
G.add_edge(1, 2)
G.add_edges_from([(2, 3), (3, 4), (4, 1)])
# 查看图的基本信息
print("节点:", G.nodes())
print("边:", G.edges())
print("节点数:", G.number_of_nodes())
print("边数:", G.number_of_edges())
有向图与加权图
# 有向图 DG = nx.DiGraph() DG.add_edge(1, 2, weight=0.6) DG.add_edge(2, 3, weight=1.0) # 加权无向图 WG = nx.Graph() WG.add_weighted_edges_from([(1, 2, 0.5), (2, 3, 0.8), (3, 1, 1.2)])
常用图算法
最短路径（Dijkstra / Bellman-Ford）
import networkx as nx
G = nx.Graph()
G.add_weighted_edges_from([(1, 2, 0.4), (2, 3, 0.8), (3, 4, 0.3), (1, 4, 1.5)])
# 最短路径
path = nx.shortest_path(G, source=1, target=4, weight='weight')
print("最短路径:", path)
# 最短路径长度
length = nx.shortest_path_length(G, source=1, target=4, weight='weight')
print("最短路径长度:", length)
最小生成树（Prim / Kruskal）
G = nx.Graph()
G.add_weighted_edges_from([(1, 2, 1), (2, 3, 2), (3, 4, 3), (4, 1, 4), (2, 4, 5)])
mst = nx.minimum_spanning_tree(G)
print("最小生成树的边:", mst.edges())
连通性分析
G = nx.Graph()
G.add_edges_from([(1, 2), (2, 3), (4, 5)])
# 连通分量
components = list(nx.connected_components(G))
print("连通分量:", components)
# 是否连通
print("是否连通:", nx.is_connected(G))
中心性分析
G = nx.karate_club_graph() # 示例图：空手道俱乐部网络
# 度中心性
degree_centrality = nx.degree_centrality(G)
print("度中心性:", degree_centrality)
# 介数中心性
betweenness_centrality = nx.betweenness_centrality(G)
print("介数中心性:", betweenness_centrality)
# 接近中心性
closeness_centrality = nx.closeness_centrality(G)
print("接近中心性:", closeness_centrality)
社区发现（Louvain / Girvan-Newman）
import community # 需要 pip install python-louvain
G = nx.karate_club_graph()
partition = community.best_partition(G)
print("社区划分:", partition)
图的可视化
import networkx as nx
import matplotlib.pyplot as plt
G = nx.karate_club_graph()
pos = nx.spring_layout(G) # 使用弹簧布局
# 绘制节点
nx.draw_networkx_nodes(G, pos, node_color='lightblue', node_size=500)
# 绘制边
nx.draw_networkx_edges(G, pos, edge_color='gray')
# 绘制标签
nx.draw_networkx_labels(G, pos, font_size=10, font_family='sans-serif')
"Karate Club Graph")
plt.axis('off')
plt.show()
其他常用库对比
| 库名 | 特点 | 适用场景 |
|---|---|---|
| NetworkX | 易用、功能丰富、支持多种图算法 | 中小规模图、教学、原型开发 |
| igraph | 高性能、支持大规模图 | 大规模网络分析 |
| Graph-tool | 基于 C++，性能极高 | 超大规模图、统计推断 |
| SciPy sparse | 稀疏矩阵操作 | 图作为邻接矩阵处理 |
实际应用场景
- 社交网络分析：朋友关系、影响力传播
- 推荐系统：用户-物品二部图
- 交通网络：最短路径、最小生成树
- 生物信息学：蛋白质相互作用网络
- Web 页面排名：PageRank 算法
进阶：PageRank 算法
G = nx.DiGraph()
G.add_edges_from([(1, 2), (1, 3), (2, 3), (3, 1), (3, 2)])
pagerank = nx.pagerank(G)
print("PageRank 值:", pagerank)
首发原创文章，作者：王坚，如若转载，请注明出处：https://idctop.com/article/478609.html
