[Python办公]一文入门图论Graphs,轻松处理最短路径等问题!
图论是研究图这种数学结构的性质和应用的学科。图(Graphs)由节点(或顶点)和连接这些节点的边组成,它是一种强大的数据结构,广泛应用于各种领域。以下举例用最短距离来入门图论。
入门问题:
已知1-8个节点相互距离如图,请求解1-8的最短距离,给出具体最短路径。
求解结果:最短路径:Shortest path from 1 to 8: [1, 2, 4, 5, 6, 7, 8], distance: 14
代码:
# 用图G求解最短路径
# author: William l50342479z
# date:20240827
import networkx as nx
import matplotlib.pyplot as plt
# 创建一个空的有向图
G = nx.DiGraph()
# 添加8个节点
nodes = range(1, 9)
G.add_nodes_from(nodes)
# 添加边和权重
edges = [
(1, 2, 1), (1, 3, 4), (2, 3, 2), (2, 4, 5), (3, 4, 3),
(3, 5, 6), (4, 5, 2), (4, 6, 7), (5, 6, 1), (5, 7, 8),
(6, 7, 2), (6, 8, 9), (7, 8, 3)
]
G.add_weighted_edges_from(edges)
# 计算从节点1到节点8的最短路径
shortest_path= nx.dijkstra_path(G, 1, 8)
shortest_path_distance= nx.dijkstra_path_length(G, 1, 8)
# 绘制图形
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue', font_size=12, font_weight='bold')
# 绘制最短路径
shortest_path_edges = [(shortest_path[i], shortest_path[i+1]) for i in range(len(shortest_path)-1)]
nx.draw_networkx_edges(G, pos, edgelist=shortest_path_edges, edge_color='red', width=2)
# 显示权重
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=10)
# 在图形上输出结果
plt.title(f"Shortest Path from 1 to 8: {shortest_path}, Distance: {shortest_path_distance}")
# 这行代码会在图形的中间位置(x=0.5)稍微偏下(y=0.05)添加文本
plt.text(0.5, 0.05, f"Shortest Path Length: {shortest_path_distance}", transform=plt.gcf().transFigure)
plt.show()
详细介绍图 G
,我们需要考虑图的几个关键属性和特征。
-
图的类型:
- 无向图(Undirected Graph): 节点之间的边没有方向。
- 有向图(Directed Graph): 节点之间的边有方向。
- 多重图(Multigraph): 允许节点之间有多条边。
-
图的创建:
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), (3, 1)])
图的属性和方法
-
节点和边的操作:
G.add_node(node)
: 添加一个节点。G.add_nodes_from(nodes)
: 从一个容器中添加多个节点。G.add_edge(u, v)
: 添加一条边。G.add_edges_from(edges)
: 从一个容器中添加多条边。
-
查询节点和边:
G.nodes()
: 返回图中所有节点的视图。G.edges()
: 返回图中所有边的视图。G.neighbors(node)
: 返回与指定节点相邻的所有节点。
-
图的连通性:
nx.is_connected(G)
: 检查图是否是连通的。nx.connected_components(G)
: 返回图中所有的连通分量。
-
路径和最短路径:
nx.shortest_path(G, source, target)
: 返回从源节点到目标节点的最短路径。nx.all_shortest_paths(G, source, target)
: 返回从源节点到目标节点的所有最短路径。
-
图的中心性:
nx.degree_centrality(G)
: 计算每个节点的度中心性。nx.betweenness_centrality(G)
: 计算每个节点的介数中心性。nx.closeness_centrality(G)
: 计算每个节点的接近中心性。
示例代码
import networkx as nx
import matplotlib.pyplot as plt
# 创建一个简单的图
G = nx.Graph()
G.add_edges_from([(1, 2), (2, 3), (3, 1), (3, 4)])
# 获取节点和边
nodes = G.nodes()
edges = G.edges()
# 检查图的连通性
is_connected = nx.is_connected(G)
# 计算最短路径
shortest_path_1_to_4 = nx.shortest_path(G, source=1, target=4)
shortest_path_distance_1_to_4 = nx.shortest_path_length(G, source=1, target=4)
# 绘制图形
plt.figure(figsize=(8, 5))
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue', font_size=12, font_weight='bold')
# 绘制最短路径
shortest_path_edges = [(shortest_path_1_to_4[i], shortest_path_1_to_4[i+1]) for i in range(len(shortest_path_1_to_4)-1)]
nx.draw_networkx_edges(G, pos, edgelist=shortest_path_edges, edge_color='red', width=2)
# 在图形上输出结果
plt.text(0.5, 0.05, f"Shortest Path Length: {shortest_path_distance_1_to_4}", transform=plt.gcf().transFigure)
plt.show()
运行结果:
这些示例代码展示了如何创建图、添加节点和边、查询图的结构、检查连通性以及计算最短路径和中心性。这些是图论分析中的基本操作,可以帮助你更好地理解和分析图 G
以下是图 G
的一些基本属性和特征,以及如何获取这些信息:
-
节点(Nodes):
- 节点是图的基本组成部分。
- 使用
G.nodes()
方法可以获取图中的所有节点。
-
边(Edges):
- 边连接图中的节点。
- 使用
G.edges()
方法可以获取图中的所有边。 - 如果是加权图,边可能有权重,可以使用
G[u][v]['weight']
来获取边(u, v)
的权重。
-
类型(Type):
- 图可以是简单的(没有自环和多边)或复杂的(可以有自环和多边)。
- 使用
G.is_directed()
方法可以检查图是否是有向的。
-
连通性(Connectivity):
- 在无向图中,连通组件是指图中任意两个节点都相互连接的节点集合。
- 使用
nx.connected_components(G)
可以找到所有连通组件。
-
度(Degree):
- 节点的度是指与该节点相连的边的数量。
- 在无向图中,使用
G.degree(node)
可以获取节点的度。 - 在有向图中,分为入度(in-degree)和出度(out-degree),可以使用
G.in_degree(node)
和G.out_degree(node)
分别获取。
-
路径(Paths):
- 路径是图中的一个序列,由边顺序连接的节点组成。
- 使用
nx.all_simple_paths(G, source, target)
可以找到所有简单路径(没有重复节点的路径)。
-
最短路径(Shortest Paths):
- 最短路径是指两个节点之间权重最小的路径。
- 使用
nx.shortest_path(G, source, target)
可以找到最短路径。
-
图的密度(Density):
- 图的密度是指图中实际存在的边数与可能存在的最大边数之比。
- 使用
nx.density(G)
可以计算图的密度。
-
聚类系数(Clustering Coefficient):
- 聚类系数是图中节点形成三角形的倾向的度量。
- 使用
nx.clustering(G)
可以计算每个节点的聚类系数。
-
中心性(Centrality):
- 中心性是图中节点重要性的度量。
- 有多种中心性度量,如度中心性、介数中心性、接近中心性等。
这些属性和特征可以帮助你更好地理解和描述图 G
。
常见用途
-
社交网络分析:
- 分析人与人之间的联系,识别社区结构,研究信息传播等。
-
网络路由和通信:
- 在计算机网络中,图用于表示网络拓扑,优化数据包的路由。
-
交通和物流:
- 表示道路、航线或铁路网络,优化货物流通路径。
-
知识图谱:
- 表示实体(如人、地点、事物)之间的关系,用于搜索引擎、推荐系统等。
-
生物信息学:
- 表示蛋白质相互作用网络,研究生物分子间的联系。
-
电力网络:
- 分析电网的拓扑结构,优化电力分配。
-
经济学和金融:
- 分析金融市场中的交易网络,识别市场风险。
总结
图论不仅是一种数学理论,也是一种实用的工具,它为解决复杂问题提供了强大的支持。通过理解图的结构和属性,我们可以更好地理解和分析现实世界中的各种关系和网络。随着技术的进步,图论的应用领域将继续扩展,为解决更多复杂问题提供新的思路和方法。
标签:图论,Python,路径,nx,Graphs,edges,path,节点,shortest From: https://blog.csdn.net/weixin_45933029/article/details/141593482