拓撲排序

拓撲排序或拓撲排序在一條直線上，即在列表中對有向非迴圈圖中的頂點進行排序，使得所有有向邊從左到右。如果圖形包含有向迴圈，則不能存在這樣的順序，因為你無法在一條直線上繼續前進並仍然返回到你開始的位置。

形式上，在圖形 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