Python实现有向无环图的拓扑排序代码示例

如果下载的源码需要作者授权,请更换源码。本站免费分享资源不会增加授权

本篇文章给大家带来的内容是关于Python实现有向无环图的拓扑排序代码示例,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

Python有向无环图的拓扑排序

拓扑排序的官方定义为:由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。而个人认为,拓扑排序即是在图的基本遍历法上引入了入度的概念并围绕入度来实现的排序方法,拓扑排序与Python多继承中mro规则的排序类似,若想深入研究mro规则的C3算法,不妨了解一下 DAG(有向无环图) 的拓扑排序。

入度:指有向图中某节点被指向数目之和
有向无环图:Directed Acyclic Graph,简称DAG,若熟悉机器学习则肯定对DAG不陌生,如ANN、DNN、CNN等则都是典型的DAG模型,对这类模型此处不再过多敷述,有兴趣的可以自行学习。

以一个有向无环图为例,如下图:

Python实现有向无环图的拓扑排序代码示例

# 定义图结构graph = {     "A": ["B","C"],     "B": ["D","E"],     "C": ["D","E"],     "D": ["F"],     "E": ["F"],     "F": [],}

如图
A的指向的元素为B、C
B的指向的元素为D、E
C的指向的元素为D、E
D的指向的元素为F
E的指向的元素为F
F的指向的元素为空
即A的入度为0,B的入度为1,C的入度为1,D的入度为2,E的入度为2,F的入度为2
在DAG的拓扑排序中,每次都选取入度为 0 的点加入拓扑队列中,再删除与这一点连接的所有边。
首先找到入度为0的点A,把A从队列中取出,同时添加到结果中并把A相关的指向移除,即B、C的入度减少1变为0并将B,C添加到队列中,再从队列首部取出入度为0的节点,以此类推,最后输出结果,完成DAG的拓扑排序。

def TopologicalSort(G):     # 创建入度字典     in_degrees = dict((u, 0) for u in G)     # 获取每个节点的入度     for u in G:         for v in G[u]:             in_degrees[v] += 1     # 使用列表作为队列并将入度为0的添加到队列中     Q = [u for u in G if in_degrees[u] == 0]     res = []     # 当队列中有元素时执行     while Q:         # 从队列首部取出元素         u = Q.pop()         # 将取出的元素存入结果中         res.append(u)         # 移除与取出元素相关的指向,即将所有与取出元素相关的元素的入度减少1         for v in G[u]:             in_degrees[v] -= 1             # 若被移除指向的元素入度为0,则添加到队列中             if in_degrees[v] == 0:                 Q.append(v)     return resprint(TopologicalSort(graph))

输出结果:

['A', 'C', 'B', 'E', 'D', 'F']

代码输出结果与上述分析相符

本文由(壳先生)整理自网络,如转载请注明出处:https://www.mrshell.com;
本站发布的内容若侵犯到您的权益,请邮件联系 i@mrshell.com 删除,我们将及时处理!
===========================================================================

1. 本站大部分下载资源收集于网络,不保证其完整性以及安全性,请下载后自行测试。
2. 本站资源仅供学习和交流使用,版权归资源原作者所有,请在下载后24小时之内自觉删除。
3. 不得使用于非法商业用途,商用请支持正版!不得违反国家法律,否则后果自负!
4. 若作商业用途,请购买正版,由于未及时购买和付费发生的侵权行为,与本站无关。
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!

=================================================================

壳先生 » Python实现有向无环图的拓扑排序代码示例

发表评论

提供最优质的资源集合

立即查看 了解详情