拓扑排序

拓扑排序或拓扑排序在一条直线上，即在列表中对有向非循环图中的顶点进行排序，使得所有有向边从左到右。如果图形包含有向循环，则不能存在这样的顺序，因为你无法在一条直线上继续前进并仍然返回到你开始的位置。

形式上，在图形 G = (V, E) 中，所有顶点的线性排序是这样的：如果 G 包含从顶点 u 到顶点 v 的边缘 (u, v) ∈ E，则 u 在排序中位于 v 之前。

值得注意的是，每个 DAG 至少有一个拓扑排序。

存在用于在线性时间内构造任何 DAG 的拓扑排序的已知算法，一个示例是：

1. 调用 depth_first_search(G) 来计算每个顶点 v 的完成时间 v.f
2. 每个顶点完成后，将其插入链表的前面
3. 链接的顶点列表，因为它现在已经排序。

由于深度优先搜索算法需要时间 12 并且需要Ω(1)（恒定时间）将每个|V|顶点插入到链表的前面，因此可以在ϴ(V + E) 时间执行拓扑排序。

许多应用程序使用有向非循环图来指示事件之间的优先级。我们使用拓扑排序，以便我们得到一个排序来处理每个顶点之前的任何顶点。

图中的顶点可以表示要执行的任务，边可以表示一个任务必须在另一个任务之前执行的约束; 拓扑排序是执行 V 中描述的任务任务集的有效序列。

问题实例及其解决方案

让一个顶点 v 描述一个 Task(hours_to_complete: int)，即 Task(4) 描述了一个 Task，它需要花费 20 个小时来完成，而一个边缘 e 描述了一个 Cooldown(hours: int)，这样 Cooldown(3) 描述了一个完成任务后冷却的持续时间。

让我们的图形称为 dag（因为它是一个有向无环图），并让它包含 5 个顶点：

A <- dag.add_vertex(Task(4)); 
B <- dag.add_vertex(Task(5));
C <- dag.add_vertex(Task(3)); 
D <- dag.add_vertex(Task(2));
E <- dag.add_vertex(Task(7));

我们将顶点与有向边连接，使图形是非循环的，

// A ---> C ----+
// |      |     |
// v      v     v
// B ---> D --> E
dag.add_edge(A, B, Cooldown(2));
dag.add_edge(A, C, Cooldown(2));
dag.add_edge(B, D, Cooldown(1));
dag.add_edge(C, D, Cooldown(1));
dag.add_edge(C, E, Cooldown(1));
dag.add_edge(D, E, Cooldown(3));

那么 A 和 E 之间有三种可能的拓扑排序，

1. A -> B -> D -> E
2. A -> C -> D -> E
3. A -> C -> E