[Python办公]一文入门图论Graphs，轻松处理最短路径等问题！

大家好，欢迎来到IT知识分享网。

图论是研究图这种数学结构的性质和应用的学科。图（Graphs）由节点（或顶点）和连接这些节点的边组成，它是一种强大的数据结构，广泛应用于各种领域。以下举例用最短距离来入门图论。

入门问题：

已知1-8个节点相互距离如图，请求解1-8的最短距离，给出具体最短路径。

求解结果：最短路径：Shortest path from 1 to 8: [1, 2, 4, 5, 6, 7, 8], distance: 14

代码：

# 用图G求解最短路径 # author: William lz # date: 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，我们需要考虑图的几个关键属性和特征。

1. 图的类型:

• 无向图（Undirected Graph）: 节点之间的边没有方向。
• 有向图（Directed Graph）: 节点之间的边有方向。
• 多重图（Multigraph）: 允许节点之间有多条边。

1. 图的创建:

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)])

图的属性和方法

1. 节点和边的操作:

• G.add_node(node): 添加一个节点。
• G.add_nodes_from(nodes): 从一个容器中添加多个节点。
• G.add_edge(u, v): 添加一条边。
• G.add_edges_from(edges): 从一个容器中添加多条边。

1. 查询节点和边:

• G.nodes(): 返回图中所有节点的视图。
• G.edges(): 返回图中所有边的视图。
• G.neighbors(node): 返回与指定节点相邻的所有节点。

1. 图的连通性:

• nx.is_connected(G): 检查图是否是连通的。
• nx.connected_components(G): 返回图中所有的连通分量。

1. 路径和最短路径:

• nx.shortest_path(G, source, target): 返回从源节点到目标节点的最短路径。
• nx.all_shortest_paths(G, source, target): 返回从源节点到目标节点的所有最短路径。

1. 图的中心性:

• 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 的一些基本属性和特征，以及如何获取这些信息：

1. 节点（Nodes）:

• 节点是图的基本组成部分。
• 使用 G.nodes() 方法可以获取图中的所有节点。

1. 边（Edges）:

• 边连接图中的节点。
• 使用 G.edges() 方法可以获取图中的所有边。
• 如果是加权图，边可能有权重，可以使用 G[u][v][‘weight’] 来获取边 (u, v) 的权重。

1. 类型（Type）:

• 图可以是简单的（没有自环和多边）或复杂的（可以有自环和多边）。
• 使用 G.is_directed() 方法可以检查图是否是有向的。

1. 连通性（Connectivity）:

• 在无向图中，连通组件是指图中任意两个节点都相互连接的节点集合。
• 使用 nx.connected_components(G) 可以找到所有连通组件。

1. 度（Degree）:

• 节点的度是指与该节点相连的边的数量。
• 在无向图中，使用 G.degree(node) 可以获取节点的度。
• 在有向图中，分为入度（in-degree）和出度（out-degree），可以使用 G.in_degree(node) 和 G.out_degree(node) 分别获取。

1. 路径（Paths）:

• 路径是图中的一个序列，由边顺序连接的节点组成。
• 使用 nx.all_simple_paths(G, source, target) 可以找到所有简单路径（没有重复节点的路径）。

1. 最短路径（Shortest Paths）:

• 最短路径是指两个节点之间权重最小的路径。
• 使用 nx.shortest_path(G, source, target) 可以找到最短路径。

1. 图的密度（Density）:

• 图的密度是指图中实际存在的边数与可能存在的最大边数之比。
• 使用 nx.density(G) 可以计算图的密度。

1. 聚类系数（Clustering Coefficient）:

• 聚类系数是图中节点形成三角形的倾向的度量。
• 使用 nx.clustering(G) 可以计算每个节点的聚类系数。

1. 中心性（Centrality）:

• 中心性是图中节点重要性的度量。
• 有多种中心性度量，如度中心性、介数中心性、接近中心性等。

这些属性和特征可以帮助你更好地理解和描述图 G。

常见用途

1. 社交网络分析:分析人与人之间的联系，识别社区结构，研究信息传播等。
2. 网络路由和通信:在计算机网络中，图用于表示网络拓扑，优化数据包的路由。
3. 交通和物流:表示道路、航线或铁路网络，优化货物流通路径。
4. 知识图谱:表示实体（如人、地点、事物）之间的关系，用于搜索引擎、推荐系统等。
5. 生物信息学:表示蛋白质相互作用网络，研究生物分子间的联系。
6. 电力网络:分析电网的拓扑结构，优化电力分配。
7. 经济学和金融:分析金融市场中的交易网络，识别市场风险。

总结

图论不仅是一种数学理论，也是一种实用的工具，它为解决复杂问题提供了强大的支持。通过理解图的结构和属性，我们可以更好地理解和分析现实世界中的各种关系和网络。随着技术的进步，图论的应用领域将继续扩展，为解决更多复杂问题提供新的思路和方法。