在有向无环图DAG中， 使用拓扑排序，将获得一个包含所有顶点的一个列表组合， 因此可以用来遍历DAG。
步骤
从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出。从图中删除该顶点和所有以它为起点的有向边。重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。
可以得到拓扑排序后的结果是 { 1, 2, 4, 3, 5 }。
通常，一个有向无环图可以有一个或多个拓扑排序序列
代码
import itertools
def topological_sort(graph
):
in_degree_dict
= dict.fromkeys
(graph
.keys
(), 0)
flattened_values
= list()
[flattened_values
.extend
(value
) for value
in graph
.values
()]
for key
, group
in itertools
.groupby
(sorted(flattened_values
), lambda x
: x
):
in_degree_dict
[key
] = len(list(group
))
result
= list()
if not all(list(map(lambda val
: val
>= 1, in_degree_dict
.values
()))):
candidates
= [key
for key
in in_degree_dict
if in_degree_dict
[key
] == 0]
while len(candidates
) > 0:
candidate
= candidates
.pop
()
result
.append
(candidate
)
for node
in graph
[candidate
]:
in_degree_dict
[node
] -= 1
in_degree_dict
.pop
(candidate
)
candidates
.extend
([key
for key
in in_degree_dict
if in_degree_dict
[key
] == 0])
else:
print("U need build a graph with one node in-degree equals 0 at least")
return result
if __name__
== '__main__':
graph_dict
= {
"A": {"B": 5, "D": 1},
"B": {"C": 2, "D": 1},
"C": {"E": 8},
"D": {"C": 4, "E": 3},
"E": {}
}
for k
, v
in graph_dict
.items
():
graph_dict
[k
] = list(v
.keys
())
path
= topological_sort
(graph_dict
)
print(path
)
参考
什么是拓扑排序（Topological Sorting） 拓扑排序(python实现)
