python 实现拓扑排序

本文参考地址：

1. https://www.cnblogs.com/zhaojieyu/p/8543136.html
2. https://blog.csdn.net/lanchunhui/article/details/50957608

一提算法也许很多人刚开始会想：好难啊，我不会。我也是，哈哈哈。但是这是基石，而语言只是实现工具。本文介绍了最近学习的一个排序，仅作个人学习使用，尽量也用自己理解的话语描述出来，如果错误，麻烦指正。

什么是拓扑排序

tuopu.png

上面两种图，圆圈中的字母有如下两个规律：

• 每个顶点出现且只出现一次；
• 若A在序列中排在B的前面，则在图中不存在从B到A的路径。
  这种具有依赖关系的排序，就是拓扑排序（Topological sorting）

应用

那这种排序在日常生活中常用吗？

1. 比如你在ubuntu 系统上使用 apt-get 安装工具或者软件，会帮你自动寻找并且下载依赖包
2. MAC brew 安装也是如此
   这种软件安装的实例就是拓扑排序。
   总结
   待完成的不同任务之间通常都会存在着某些依赖关系，这些依赖关系会为它们的执行顺序行程表部分约束。对于这种依赖关系，很容易将其表示成一个有向无环图（Directed Acyclic Graph，DAG，无环是一个重要条件），并将寻找其中依赖顺序的过程

用python 实现

如上图，使用python 实现并输出依赖关系列表

要求输出正确的拓扑排序

# 出度为0（即没有指向其它节点的箭头）的节点排在最前面，排序的过程就是依次将出度为0的节点移出来，所形成的结果即是最终排序了
# 下面是代码实现
#!/usr/bin/python3
# -*- coding: UTF-8 -*-
def toposort(graph):
    in_degrees = dict((u,0) for u in graph)   #初始化所有顶点入度为0
    vertex_num = len(in_degrees)
    for u in graph:
        for v in graph[u]:
            in_degrees[v] += 1       #计算每个顶点的入度
    print(in_degrees)
    Q = [u for u in in_degrees if in_degrees[u] == 0]   # 筛选入度为0的顶点
    print(Q)
    Seq = []
    while Q:
        u = Q.pop()       #默认从最后一个删除
        Seq.append(u)
        for v in graph[u]:
            in_degrees[v] -= 1       #移除其所有指向
            if in_degrees[v] == 0:
                Q.append(v)          #再次筛选入度为0的顶点
    if len(Seq) == vertex_num:       #如果循环结束后存在非0入度的顶点说明图中有环，不存在拓扑排序
        return Seq
    else:
        print("there's a circle.")
if __name__ == '__main__':

    G = {
        'a':'bf',
        'b':'cdf',
        'c':'d',
        'd':'ef',
        'e':'f',
        'f':''
    }
    t=toposort(G)
    print(t[::-1])