第四部分：系統最佳化¶
< 上一題：頻寬容量分析 | 返回目錄 | 下一題：傳輸成本最小化 >
場景：路由器升級順序怎麼排？¶
你要把所有資料中心的路由器從 v3 升級到 v4。但有依賴關係：
- 核心路由器必須**先於**邊緣路由器升級
- 東京必須**先於**台北升級（因為台北的備援指向東京）
- ...
這些「先後關係」形成了一個有向圖。你需要找出一個**合法的升級順序**。
「有依賴關係的任務，怎麼排序才不會違反依賴？」
第 8 題：部署順序規劃 - 拓撲排序與 DAG¶
(a) DAG 與拓撲排序定義¶
3 分 ・ 大二
你需要知道：什麼情況下能找到合法順序？
題目：
-
定義 DAG（有向無環圖）
-
定義**拓撲排序（Topological Sort）**
-
證明：有向圖有拓撲排序 \(\Leftrightarrow\) 它是 DAG
解答
1. DAG：
Directed Acyclic Graph，有向無環圖。
- 有向：邊有方向
- 無環：不存在從某點出發又回到自己的路徑
2. 拓撲排序：
將 DAG 的頂點排成一個線性序列 \(v_1, v_2, ..., v_n\)，使得對於每條邊 \((v_i, v_j)\)，都有 \(i < j\)。
直覺：「依賴的東西排在前面」。
3. 證明：
→（DAG 有拓撲排序）：
DAG 一定有至少一個**入度為 0** 的頂點（否則沿著邊反向走，必會回到起點，形成環）。
拿掉這個頂點和它的出邊，剩下的還是 DAG。遞迴處理。
←（有拓撲排序 → 無環）：
假設有環 \(v_{i_1} \to v_{i_2} \to ... \to v_{i_k} \to v_{i_1}\)。
拓撲序要求 \(i_1 < i_2 < ... < i_k < i_1\)，矛盾。
(b) DFS-based 拓撲排序¶
3 分 ・ 大三
你需要知道：如何用 DFS 產生拓撲序？
題目：
-
說明 DFS-based 拓撲排序的步驟
-
實現演算法
-
如何同時偵測是否存在環？
解答
1. DFS-based 拓撲排序：
核心觀察：DFS 的「結束時間」反過來就是拓撲序。
當一個節點的所有後繼都處理完後，它才「結束」。所以結束越晚的，依賴越少，應該排在越前面。
2. 實現：
def topological_sort_dfs(graph, V):
visited = [False] * V
stack = []
def dfs(u):
visited[u] = True
for v in graph[u]:
if not visited[v]:
dfs(v)
stack.append(u) # 結束時加入
for u in range(V):
if not visited[u]:
dfs(u)
return stack[::-1] # 反轉
3. 環偵測：
用三種狀態：未訪問、訪問中、已完成。
def topological_sort_with_cycle_detection(graph, V):
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * V
stack = []
def dfs(u):
color[u] = GRAY
for v in graph[u]:
if color[v] == GRAY:
return False # 發現環！
if color[v] == WHITE and not dfs(v):
return False
color[u] = BLACK
stack.append(u)
return True
for u in range(V):
if color[u] == WHITE:
if not dfs(u):
return None # 有環
return stack[::-1]
GRAY → GRAY：在 DFS 樹中從某節點走回祖先 → 有環。
© Kahn's Algorithm（BFS-based）¶
3 分 ・ 大三
你需要知道：另一種拓撲排序方法
題目：
-
說明 Kahn's Algorithm（基於入度的 BFS）
-
實現演算法
解答
1. Kahn's Algorithm：
- 計算每個頂點的入度
- 把入度為 0 的頂點放入 Queue
- 重複：
- 取出一個頂點 \(u\)，加入結果
- 把 \(u\) 的所有出邊刪除（對應頂點入度 -1）
- 如果某頂點入度變成 0，加入 Queue
- 如果結果長度 \(\neq V\)，表示有環
2. 實現：
from collections import deque
def topological_sort_kahn(graph, V):
in_degree = [0] * V
for u in range(V):
for v in graph[u]:
in_degree[v] += 1
queue = deque([u for u in range(V) if in_degree[u] == 0])
result = []
while queue:
u = queue.popleft()
result.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
if len(result) != V:
return None # 有環
return result
時間複雜度：\(O(V + E)\)
(d) DAG 最長路徑（Critical Path）¶
4 分 ・ 大三
你需要知道：升級所有路由器**最少需要多久**？
如果每個路由器升級時間不同，且有依賴關係，整體完成時間取決於**最長路徑（Critical Path）**。
題目：
-
說明如何在 DAG 上求最長路徑
-
時間複雜度是多少？
解答
1. DAG 最長路徑：
方法：拓撲排序 + DP
def dag_longest_path(graph, V, weights):
# weights[u] = 頂點 u 的處理時間
topo_order = topological_sort_kahn(graph, V)
dist = [0] * V
for u in topo_order:
for v in graph[u]:
dist[v] = max(dist[v], dist[u] + weights[u])
# 還要加上終點自己的時間
return max(dist[u] + weights[u] for u in range(V))
思路： - 按拓撲序處理，保證處理 \(v\) 時，所有 \(v\) 的前驅都已處理 - \(dist[v]\) = 從任意起點到 \(v\)（不含 \(v\)）的最長路徑
2. 時間複雜度：\(O(V + E)\)
注意：一般圖的最長路徑是 NP-hard，但 DAG 可以多項式時間解決！
進階挑戰：計算拓撲序數量¶
3 分 ・ 碩一
你需要知道：給定 DAG，有多少種不同的合法拓撲序？
解答
方法：狀態壓縮 DP
設 \(dp[S]\) = 已選頂點集合為 \(S\) 時的拓撲序數量。
def count_topological_orders(graph, V):
in_degree_original = [0] * V
for u in range(V):
for v in graph[u]:
in_degree_original[v] += 1
dp = {0: 1}
for _ in range(V):
new_dp = defaultdict(int)
for mask, count in dp.items():
in_degree = in_degree_original.copy()
for u in range(V):
if mask & (1 << u):
for v in graph[u]:
in_degree[v] -= 1
for u in range(V):
if not (mask & (1 << u)) and in_degree[u] == 0:
new_dp[mask | (1 << u)] += count
dp = new_dp
return dp.get((1 << V) - 1, 0)
時間複雜度：\(O(2^V \cdot V)\)
只適用於 \(V\) 很小的情況。
第 8 題小結：你的依賴管理工具箱¶
「有依賴的任務怎麼排序？」
│
├─► (a) 什麼時候有解？→ DAG（無環）
│
├─► (b) 怎麼排序？→ DFS（結束時間反轉）
│ → 順便偵測環
│
├─► (c) 另一種方式？→ Kahn（入度 BFS）
│ → 直覺清晰
│
└─► (d) 要花多久？→ Critical Path
→ DAG 上 DP，O(V+E)
| 演算法 | 方法 | 時間 |
|---|---|---|
| DFS 拓撲排序 | 結束時間反轉 | \(O(V+E)\) |
| Kahn's | 入度 BFS | \(O(V+E)\) |
| DAG 最長路徑 | 拓撲序 + DP | \(O(V+E)\) |