Topological Sort

拓扑排序

入度(In-degree)：有向图(Directed Graph)中指向当前节点的点的个数(或指向当前节点的边的条数)

步骤：

1. 统计每个点的入度
2. 将每个入度为 0 的点放入队列(Queue)中作为起始节点
3. 不断从队列中拿出一个点，
   1. 去掉这个点的所有连边(指向其他点的边)，
      1. 其他点的相应的入度 - 1
      2. 一旦发现新的入度为 0 的点，丢回队列中

拓扑排序并不是传统的排序算法
一个图可能存在多个拓扑序(Topological Order)，也可能不存在任何拓扑序

拓扑排序的四种不同问法

1. 求任意一个拓扑序
2. 问是否存在拓扑序
3. 求是否存在且仅存在一个拓扑序
4. 求字典序最小的拓扑排序

---

求任意一个拓扑排序

一个个把点从图中抠出来

---

判断是否存在拓扑排序

所有节点均能从图中被删除进入拓扑序

---

问拓扑序是否唯一

保持队列中有且仅有一个元素

---

求字典序最小的拓扑排序

优先队列

alienOrder