Python dag有向图数据结构与算法——拓扑排序

86 阅读 0 评论 57 点赞

我是靠谱客的博主怡然小蜜蜂，这篇文章主要介绍Python dag有向图数据结构与算法——拓扑排序，现在分享给大家，希望可以做个参考。

参考：https://blog.csdn.net/lanchunhui/article/details/50957608
有向图

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
Python 数据结构与算法——拓扑排序
几乎在所有的项目，甚至日常生活，待完成的不同任务之间通常都会存在着某些依赖关系，这些依赖关系会为它们的执行顺序行程表部分约束。对于这种依赖关系，很容易将其表示成一个有向无环图（Directed Acyclic Graph，DAG，无环是一个重要条件），并将寻找其中依赖顺序的过程称为拓扑排序（topological sorting）。
很多情况下，拓扑排序问题往往会出现在一些中等复杂程度的计算系统中。这方面最典型的例子莫过于软件安装了，现在大多数操作系统都至少会有一个自动安装软件组件的系统（Ubuntu Linux 系统中的 apt-get，CentOS Linux 系统中的 RPM，Mac OS X 系统中的 brew 等），这些系统会自动检测依赖关系中缺少的部分，并下载安装它们，对于这一类工作，相关组件就必须按照一定的拓扑顺序来安装。
DAG 分析
（1）拓扑排序并不唯一
（2）不含回路的有向图（有向无环图）——一定存在拓扑排序。
归简法解 DAG
归简法求解拓扑排序，第一直觉是先移除其中一个节点（后面会说，每次移除的都是当前拓扑结构中的入度为零的点，入度为 0 的含义不依赖其他任何节点，即可发生），然后解决其余 n-1 个节点的问题。
def topsort(G):
in_degrees = dict((u, 0) for u in G)
for u in G:
for v in
G[u]:
in_degrees[v] += 1
# 每一个节点的入度
Q = [u for u in G if in_degrees[u] == 0]
# 入度为 0 的节点
S = []
while Q:
u = Q.pop()
# 默认从最后一个移除
S.append(u)
for v in G[u]:
count[v] -= 1
# 并移除其指向
if count[v] == 0:
Q.append(v)
return S
对上图而言，我们使用邻接表的dict 形式进行表示：
G = {
'a':'bf',
'b':'cdf',
'c':'d',
'd':'ef',
'e':'f',
'f':''
}
>>> print(topsort(G))
['a', 'b', 'c', 'd', 'e', 'f']