首页 > 编程语言 >[Python办公]一文入门图论Graphs,轻松处理最短路径等问题!

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

时间:2024-08-31 10:22:45浏览次数:13  
标签:图论 Python 路径 nx Graphs edges path 节点 shortest

        [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,我们需要考虑图的几个关键属性和特征。

  1. 图的类型:

    • 无向图(Undirected Graph): 节点之间的边没有方向。
    • 有向图(Directed Graph): 节点之间的边有方向。
    • 多重图(Multigraph): 允许节点之间有多条边。
  2. 图的创建:

    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): 从一个容器中添加多条边。
  2. 查询节点和边:

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

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

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

    • 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() 方法可以获取图中的所有节点。
  2. 边(Edges):

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

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

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

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

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

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

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

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

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

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

常见用途

  1. 社交网络分析:

    • 分析人与人之间的联系,识别社区结构,研究信息传播等。
  2. 网络路由和通信:

    • 在计算机网络中,图用于表示网络拓扑,优化数据包的路由。
  3. 交通和物流:

    • 表示道路、航线或铁路网络,优化货物流通路径。
  4. 知识图谱:

    • 表示实体(如人、地点、事物)之间的关系,用于搜索引擎、推荐系统等。
  5. 生物信息学:

    • 表示蛋白质相互作用网络,研究生物分子间的联系。
  6. 电力网络:

    • 分析电网的拓扑结构,优化电力分配。
  7. 经济学和金融:

    • 分析金融市场中的交易网络,识别市场风险。

总结

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

标签:图论,Python,路径,nx,Graphs,edges,path,节点,shortest
From: https://blog.csdn.net/weixin_45933029/article/details/141593482

相关文章

  • Python数据清洗基础
    在Python中进行数据清洗和可视化是一个多步骤的过程,涉及到数据的读取、预处理、分析和图形表示。以下是一些关键步骤和代码示例,这些步骤可以帮助你从原始数据中提取有价值的信息,并以直观的方式展示。数据清洗读取数据:importpandasaspddata=pd.read_csv('data.csv')处......
  • [Python知识点]list列表append()和extend()的区别
    在Python中,list.append()和list.extend()都是列表(list)的方法,用于添加元素,但它们的工作方式有所不同:list.append(x):这个方法将对象x添加到列表的末尾。x可以是任何数据类型,包括列表。如果x是一个列表,那么这个列表会被作为一个单个元素添加到原列表的末尾。list.extend(itera......
  • 6种有效的时间序列数据特征工程技术(使用Python)
    在商业分析中,"时间"是一个核心概念。我们基于时间组件来分析销售数据、收入、利润、增长,甚至进行预测。然而,对于初学者来说,这可能是一个复杂的主题。在处理时间敏感的数据集时,需要考虑时间序列数据的多个细微方面。在这个领域,没有放之四海而皆准的方法。我们不必总是强制使用传......
  • python学习总结--面向对象
    1.面向对象(上)1.1定义面向对象编程:oop[objectorientedprogramming]是一种python的编程思路;面向过程:就是我们一开始学习的,按照解决问题的步骤去写代码【根据业务逻辑去写代码】,在思考问题的时候,首先分析'怎么按照步骤去实现'然后将问题解决拆解成若干个步骤,并将这些步骤对......
  • 【python】PyQt5中富文本框QTextEdit的详细教程与应用实战
    ✨✨欢迎大家来到景天科技苑✨✨......
  • python 绘制双y轴,将折线加粗并在折线上做标记
    之前的笔记折线实在是太细了,并且还有点透明,放在论文中特别难看,现在修改一下折线,并且绘制双y轴 #!usr/bin/envpython#-*-coding:utf-8_*-"""@author:Suyue@file:jakjdklj.py@time:2024/08/30{DAY}@desc:"""importpandasaspdimportmatplotlibimportmatplo......
  • 探索Python中的拼音魔法:pypinyin库的奇妙之旅
    文章目录探索Python中的拼音魔法:pypinyin库的奇妙之旅背景:为何选择pypinyin?库简介:pypinyin是什么?安装指南:如何将pypinyin纳入你的项目?功能探索:pypinyin的五大核心函数实战演练:pypinyin在不同场景下的应用常见问题:使用pypinyin时的三个常见bug及解决方案总结:pypinyin-你......
  • python办公自动化:使用`Python-PPTX`创建和操作表格
    表格是演示文稿中用于组织和显示数据的重要工具。使用Python-PPTX库,您可以在幻灯片中创建和自定义表格,包括设置表格的大小、格式和内容。本节将介绍如何使用Python-PPTX库创建表格并进行各种操作。1创建基本表格在Python-PPTX中,表格是通过add_table()方法创建的。您需要......
  • Python数据分析的数据导入和导出
    数据分析的数据的导入和导出前言一、导入数据导入Excel表格数据read_excel示例导入CSV格式数据read_csv()示例导入JSON格式数据JSON简介pandas导入JSON数据read_json()导入txt文件read_table示例导入(爬取)网络数据read_html()示例二、输出数据CSV格式数据输出to_csv示......
  • python文件打开方式详解——a、a+、r+、w+、rb、rt区别
    在做深度学习大作业的时候看到了这个代码:一开始以为“rb”是相对路径的意思,搜了一下结果不是。1.排除文件打开方式错误:r只读,r+读写,不创建,即需要事先存在一个文件以供读/读写,若不存在文件会报错w新建只写,w+新建读写,二者都会将文件内容清零,即事先不需要有该文件存在,若已经存在......