拓扑排序

若任务B必须等任务A完成后才能开始，可以用A指向B的边表示先后关系。拓扑顺序把所有顶点排成序列，并要求每条这样的边都朝向序列后面；它解决的是约束能否共同满足，以及一种可行次序是什么。

互不约束的两个任务可以交换位置，因此一个图可能拥有多个拓扑顺序。顺序本身也没有规定任务持续多久、在哪个处理器运行或实际何时开始；这些属于在依赖之上进一步建立的调度问题。

参考：[1]

若A必须在B前，B必须在C前，而C又必须在A前，就无法把三者排进一个满足所有严格先后关系的线性序列。一般地，有向图存在拓扑顺序，当且仅当它没有有向环。

因此，排序接口还要能报告“不存在”，而不是强行截断某条边后把任意输出称为有效次序。发现环可能提示依赖记录不一致，也可能表明实际对象需要不同于严格先后关系的模型，应回到边的含义判断。

参考：[1]

一种构造方法先检查有向环，再执行深度优先搜索。一个顶点的可继续分支处理完成时，把它记入后序；将该次序反转，就得到有向无环图的拓扑顺序。不能把同样的反转规则不加检查地套到存在环的图上。

采用邻接表时，判环和遍历都能在O(V+E)时间范围内进行。实现还需要覆盖没有从同一个根可达的部分，避免只排列某一块依赖网络，就误报整张图已经处理完成。

参考：[1]