链接：深入理解拓扑排序（Topological sort)

对于任何有向图而言，其拓扑排序为其所有结点的一个线性排序（对于同一个有向图而言可能存在多个这样的结点排序）。该排序满足这样的条件——对于图中的任意两个结点u和v，若存在一条有向边从u指向v，则在拓扑排序中u一定出现在v前面。

$校招必会

310. 最小高度树

拓扑排序存在的前提

当且仅当一个有向图为有向无环图（directed acyclic graph，或称DAG）时，才能得到对应于该图的拓扑排序。每一个有向无环图都至少存在一种拓扑排序

拓扑排序的算法和实现

拓扑排序的问题存在一个线性时间解。也就是说，若有向图中存在n个结点，则我们可以在O(n)时间内得到其拓扑排序，或在O(n)时间内确定该图不是有向无环图，也就是说对应的拓扑排序不存在。

要想完成拓扑排序，我们每次都应当从入度为0的结点开始遍历。因为只有入度为0的结点才能够成为拓扑排序的起点。否则根据拓扑排序的定义，只要一个结点v的入度不为0，则至少有一条边起始于其他结点而指向v，那么这条边的起点在拓扑排序的顺序中应当位于v之前，则v不能成为当前遍历的起点。

实现方法：bfs和dfs

例题

207. 课程表