拓撲排序

習題預習

1. 有一個有向無環圖(DAG) G，請問是否存在一種頂點排序，使得對於所有的邊 (u,v)， u 在排序中出現在 v 之前？

2. 在一個旅遊路線上有多個城市，每兩個城市之間有可能有多依賴關係，建立一個依賴圖，請求出任何一種不矛盾的遊覽序列，使得遊覽序列中的任何一個城市的依賴先於該城市出現。

3. 有一個項目列表，其中每個項目可能有前置項目，若要完成目標項目，請問最少需要完成多少個項目，以及需要以甚麼順序完成才能完成目標項目。

4. 當機器需要先後安裝多個軟體程式時，若程式之間可能存在依賴關係，請問是否能夠找到一個安裝順序，使得每個程式都有其依賴的所有程式都已經安裝完畢。

5. 有一個有向圖，請問是否存在一種頂點排序，使得圖上的所有最短路徑都是按照排序中的順序而定義的，其中最短路徑是指任意兩個頂點之間的最短路徑。

說明知識

Topological Sort是一種圖算法，主要用於拓撲分析，用於確定簡單有向無環圖中節點的線性順序。簡單來說，拓撲排序可以將有向無環圖中的節點排序，使得所有的有向邊從前面的節點指向後面的節點。

這種排序算法通常用於任務調度和依賴關係的確定。例如，在軟件項目中，拓撲排序可以用於確定任務執行順序或代碼構建的順序。在生活中，拓撲排序可以用於確定各種任務的優先級，例如，基於問題的優先級計劃執行順序，或根據直覺制定待辦事項清單。

以下是對如何進行拓撲排序算法的簡單步驟：

1. 選擇一個沒有入度的頂點
2. 去掉該頂點，以及以它為起點的邊
3. 重複1和2，直到圖為空

舉個例子：如下圖所示：

4 -> 1 -> 3 -> 5
^         |
|_________|

對該圖進行拓撲排序，按照上述步驟，我們可以得到以下結果：[2, 4, 1, 3, 5]，其中，數字表示節點編號，以此為順序，每個節點都沒有向前的有向邊。

一個比較複雜的例子：

8 -> 2 -> 3 -> 6 -> 7
|         |    |
v         v    v
1 -> 4 -> 5    9

對該圖進行拓撲排序，可以得到以下結果：[1, 8, 2, 3, 4, 5, 6, 7, 9]

彙總重點

1. 定義：Topological Sort 是一種對有向無環圖（DAG）進行節點排序的演算法。

2. 應用：Topological Sort 常用於尋找項目間的先後關係，例如工作流程中的先後順序、課程選修的先後等。

3. 步驟：Topological Sort 的步驟為尋找 DAG 的一個非循環路徑，並依照該路徑的順序將節點排序。

4. 實現方法：Topological Sort 可以使用 DFS 或 BFS 兩種方式來實現，其中 BFS 的時間複雜度較低。

5. 結果：Topological Sort 的結果並不唯一，可能存在多種排序結果。

6. 特殊情況：如果 DAG 中存在環路則無法進行 Topological Sort，這時需要進行環路檢測或者使用其他方法進行排序。

7. 應用範例：如下圖所示，該 DAG 表示六個項目之間的先後關係，使用 Topological Sort 可以得到的一個排序結果為 B, D, A, C, F, E。

   

知識測驗

1. 在有向無環圖（DAG）中，給出每個節點的入度和出度，請求出一個合法的繞行順序。

答案： Topological Sort

2. 給定有向加權圖，請找出所有最長 (加權和最大) 的簡單路徑。

答案： DAG上的最長路

3. 在有向無環圖（DAG）中，有若干個程式需要運行，但各程式之間有依賴關係，請你按照順序運行程式，使得每個程式都可以運行。

答案： Topological Sort

4. 給定一個圖，要求你從中找到一個簡單環，並且最長邊的長度最小。

答案： DAG上的最長路

5. 已知一個無向圖中所有邊的權值為1，求圖中所有圖的直徑的最小值。

答案：DAG上的最長路