Python实现拓扑算法的示例
作者:福州司马懿 时间:2023-12-09 15:06:29
前言
拓扑排序是图论中一种重要的排序算法,用于对有向无环图(DAG)进行排序。在拓扑排序中,图的顶点表示任务,有向边表示任务之间的依赖关系。拓扑排序算法可以找到一种满足所有任务依赖关系的顺序。
算法原理
拓扑排序算法的基本原理如下:
创建一个空的排序结果列表。
找到图中所有入度为0的顶点(即没有依赖关系的顶点),将其加入排序结果列表。
移除该顶点以及与其相关的边。
重复步骤2和3,直到图中的所有顶点都被处理。
如果排序结果列表的长度等于图中的顶点数,则拓扑排序成功;否则,图中存在环,无法进行拓扑排序。
Python实现
下面是使用Python实现拓扑排序算法的示例代码:
from collections import deque
def topological_sort(graph):
? ? # 统计每个顶点的入度
? ? in_degree = {v: 0 for v in graph}
? ? # 计算每个顶点的入度
? ? for v in graph:
? ? ? ? for neighbor in graph[v]:
? ? ? ? ? ? in_degree[neighbor] += 1
? ? # 将入度为0的顶点加入队列
? ? queue = deque([v for v in graph if in_degree[v] == 0])
? ? # 保存拓扑排序的结果
? ? result = []
? ? while queue:
? ? ? ? # 取出队列中的顶点
? ? ? ? v = queue.popleft()
? ? ? ? result.append(v)
? ? ? ? # 移除顶点及其相关边
? ? ? ? for neighbor in graph[v]:
? ? ? ? ? ? in_degree[neighbor] -= 1
? ? ? ? ? ? if in_degree[neighbor] == 0:
? ? ? ? ? ? ? ? queue.append(neighbor)
? ? # 判断是否存在环
? ? if len(result) != len(graph):
? ? ? ? raise ValueError("图中存在环,无法进行拓扑排序。")
? ? return result
# 测试
graph = {
? ? 'A': ['B', 'C'],
? ? 'B': ['D'],
? ? 'C': ['D', 'E'],
? ? 'D': ['F'],
? ? 'E': ['F'],
? ? 'F': []
}
try:
? ? result = topological_sort(graph)
? ? print("拓扑排序结果:", result)
except ValueError as e:
? ? print(e)
以上代码中,graph表示图的邻接表表示法,其中每个顶点表示为一个键,其对应的值为一个列表,列表中存储了与该顶点有直接边相连的顶点。
运行代码后,将输出拓扑排序的结果。
这就是使用Python实现拓扑排序算法的示例代码。通过这个算法,我们可以对有向无环图进行
排序,找到满足任务依赖关系的顺序。
来源:https://blog.csdn.net/chy555chy/article/details/130938158
标签:Python,拓扑算法
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
python将二维数组升为一维数组或二维降为一维方法实例
2023-07-25 07:51:59
![](https://img.aspxhome.com/file/2023/3/61713_0s.png)
如何将PySpark导入Python的放实现(2种)
2022-10-21 02:12:16
Python面向对象程序设计类的多态用法详解
2021-05-28 20:21:29
Oracle 存储过程加密方法
2009-10-23 18:02:00
Python实现的将文件每一列写入列表功能示例【测试可用】
2022-12-05 15:12:31
![](https://img.aspxhome.com/file/2023/8/67408_0s.png)
C#实现的ACCESS数据库操作类完整实例
2024-01-20 02:57:36
python中常用的各种数据库操作模块和连接实例
2024-01-18 16:29:20
python实现按首字母分类查找功能
2023-10-13 11:05:09
python实现翻转棋游戏(othello)
2022-06-02 10:40:19
![](https://img.aspxhome.com/file/2023/9/125049_0s.jpg)
Python基于分水岭算法解决走迷宫游戏示例
2021-08-04 17:41:37
GridView自定义分页的四种存储过程
2024-01-27 09:52:25
![](https://img.aspxhome.com/file/2023/4/96164_0s.jpg)
perl生成特定碱基比例的随机序列的代码
2023-12-08 05:27:07
用python的requests第三方模块抓取王者荣耀所有英雄的皮肤实例
2023-11-27 01:27:23
![](https://img.aspxhome.com/file/2023/4/90624_0s.jpg)
mysql中的general_log(查询日志)开启和关闭
2024-01-19 01:49:10
![](https://img.aspxhome.com/file/2023/5/91445_0s.png)
python实现报表自动化详解
2021-12-31 04:28:14
![](https://img.aspxhome.com/file/2023/3/123663_0s.jpg)
vue模仿网易云音乐的单页面应用
2024-04-10 13:48:23
双击编辑功能如何实现
2008-02-26 16:17:00
python对象销毁实例(垃圾回收)
2022-07-29 06:22:14
Python制作一个仿QQ办公版的图形登录界面
2021-06-23 20:08:49
![](https://img.aspxhome.com/file/2023/1/101611_0s.png)
Vue2.0 axios前后端登陆拦截器(实例讲解)
2023-07-02 16:59:11
![](https://img.aspxhome.com/file/2023/9/139869_0s.jpg)