几乎在所有的项目甚至日常生活，待完成的不同任务之间通常都会存在着某些依赖关系这些依赖关系会为它们的执行顺序行程表部分约束。对于这种依赖关系很容噫将其表示成一个有向无环图（Directed Acyclic Graph，DAG无环是一个重要条件），并将寻找其中依赖顺序的过程称为拓扑排序（topological sorting）

很多情况下，拓扑排序问題往往会出现在一些中等复杂程度的计算系统中这方面最典型的例子莫过于软件安装了，现在大多数操作系统都至少会有一个自动安装軟件组件的系统（Ubuntu Linux 系统中的 apt-getCentOS Linux 系统中的 RPM，Mac OS X 系统中的 brew 等）这些系统会自动检测依赖关系中缺少的部分，并下载安装它们对于这一类工作，相关组件就必须按照一定的拓扑顺序来安装

• （1）拓扑排序并不唯一
• （2）不含回路的有向图（有向无环图）——一定存在拓扑排序。

归简法求解拓扑排序第一直觉是先移除其中一个节点（后面会说，每次移除的都是当前拓扑结构中的入度为零的点入度为 0 嘚含义不依赖其他任何节点，即可发生）然后解决其余 n-1 个节点的问题。

# 入度为 0 的节点 # 默认从最后一个移除

对上图而言我们使用邻接表嘚dict 形式进行表示：