Python实现拓扑算法的示例
作者:福州司马懿 发布时间:2023-12-09 15:06:29
标签:Python,拓扑算法
前言
拓扑排序是图论中一种重要的排序算法,用于对有向无环图(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
0
投稿
猜你喜欢
- 题记JS中的this指向一直是个让初学者头疼的问题。今天,我们就一起来瞅瞅this倒地是咋回事,详细说说this指向原则,从此不再为了thi
- froglt 的站点:http://www.go2here.net 欢迎转载,请注明出处,未经作者允许,禁止一切商业应用。这是即
- 本文实例讲述了golang操作mongodb的方法。分享给大家供大家参考。具体实现方法如下:package mainimport (&nbs
- 语法:列表 list.pop(obj=list[-1])pop()用于删除并返回列表中的一个元素(默认为最后一个元素)obj:要删除并返回的
- 本文实例讲述了Python使用lambda表达式对字典排序操作。分享给大家供大家参考,具体如下:lambda表达式也常用于字典排序,既然写到
- 问题是:输入一个数字,按照指定要求逆序输出该数字,很简单,下面是实现:#!usr/bin/env python#encoding:utf-8
- 本文分析了Python出现segfault错误解决方法。分享给大家供大家参考,具体如下:最近python程序在运行过程中偶尔会引发系统seg
- ORACLE访问SQL SERVER数据库有一篇《Oracle 异构服务实践》讲得很清楚。但里面没有讲如何设置访问多个SQL Server数
- 虽然说表单验证在客户端使用javascript来验证已经可以了,但是我们为了防止访客绕过客户端验证也为了数据安全最好还是在服务器端加上必要的
- 淡入淡出图片轮换轮播效果,可以做新闻图片推荐需要的拿去用,效果预览请点击运行代码相关效果推荐:迅雷首页新闻图片轮播效果js源码 <!D
- 这篇文章详细的介绍了Oracle数据库SQL语句性能调整的基本原则,具体内容请参考下文。一、问题的提出在应用系统开发初期,由于开发数据库数据
- 本文实例讲述了Python socket套接字实现C/S模式远程命令执行功能。分享给大家供大家参考,具体如下:一. 前言要求: 使用pyth
- 问题你想将一个多层嵌套的序列展开成一个单层列表解决方案可以写一个包含 yield from 语句的递归生成器来轻松解决这个问题。比如:fro
- 首先第一步,打开文件,有两个函数可供选择:open() 和 file()①. f = open('file.txt
- 项目中使用的日志库是使用python官方库logging封装的,但是居然一直么有设置日志自动滚动,经常会受到告警说哪台机器磁盘空间又满,清理
- 前言subprocess库提供了一个API创建子进程并与之通信。这对于运行生产或消费文本的程序尤其有好处,因为这个API支持通过新进行的标准
- <% Function cutbadchar(str) badstr="不|文|明
- 最近需要用Python写一个简易通讯录,但是对于数据存储很发愁。大家都知道,使用 Python 中的列表和字典进行存储数据是很不靠谱的,所以
- 这里首先给出来我很早之前写的一篇博客,Python实现去除列表中重复元素的方法小结【4种方法】,感兴趣的话可以去看看,今天是在实践过程中又积
- 小编想把用python将列表[1,1,1,1,1,1,1,1,1,1] 和 列表 [2,2,2,2,2,2,2,2,2,2]对应相加成[3,