Python图的拓扑排序

Python有向无环图的拓扑排序

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

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

以一个有向无环图为例，如下图：

# 定义图结构
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(0)# 将取出的元素存入结果中res.append(u)# 移除与取出元素相关的指向，即将所有与取出元素相关的元素的入度减少1for v in G[u]:in_degrees[v] -= 1# 若被移除指向的元素入度为0，则添加到队列中if in_degrees[v] == 0:Q.append(v)return res
print(TopologicalSort(graph))

输出结果：

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

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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！