題目描述:給定 numCourses 門課程(編號 0 到 numCourses-1)以及先修要求陣列 prerequisites,其中 prerequisites[i] = [ai, bi] 表示選修課程 ai 前必須先修完課程 bi。請回傳一個合法的修課順序;若存在循環依賴(無法完成所有課程),則回傳空陣列。
解題思路:此題是拓撲排序的經典應用。我們將課程視為有向圖的節點,先修關係視為有向邊,問題等價於「找出有向無環圖(DAG)的拓撲排序,若圖有環則無解」。
使用 Kahn's Algorithm(BFS 版拓撲排序):
prerequisites[i] = [a, b] 代表邊 b → a,因此 adj[b].push_back(a) 且 indegree[a]++。numCourses,則回傳此順序;否則代表圖中有環,回傳空陣列。Kahn's Algorithm 的直覺:入度為 0 的節點表示「所有先修課程已完成」,可以安全修讀。每修完一門課,相當於移除這條邊,更新後續課程的入度。
時間複雜度:O(V + E) — 其中 V = numCourses(節點數),E = prerequisites.size()(邊數)。建圖需要 O(E),BFS 每個節點和每條邊各處理一次,共需 O(V + E)。
空間複雜度:O(V + E) — 鄰接表儲存所有邊需要 O(E),入度陣列和修課順序各需 O(V),BFS 佇列最壞情況下需要 O(V)。
1. Build adjacency list adj[] and indegree[] array from prerequisites
- For each [course, prereq]: adj[prereq].append(course), indegree[course]++
2. Initialize BFS queue with all nodes where indegree[i] == 0
3. While queue is not empty:
a. Dequeue node, append to order[]
b. For each neighbor of node:
- Decrement indegree[neighbor]
- If indegree[neighbor] == 0: enqueue neighbor
4. If len(order) == numCourses: return order
5. Else: return [] (cycle detected)DFS 後序拓撲排序 O(V+E):使用 DFS 並追蹤三種節點狀態(未訪問、訪問中、已完成)。若在 DFS 過程中遇到「訪問中」的節點,表示存在環,回傳空陣列。否則在後序(post-order)時將節點加入結果,最後反轉即為拓撲順序。與 Kahn's Algorithm 相比,DFS 版本更直覺地對應「遞迴展開」的概念,但需要額外維護狀態陣列。
Union-Find 環偵測 O(E·α(V)):可用於偵測是否有環,但無法直接給出拓撲順序。適合只需判斷「能否修完所有課程」的 Course Schedule I,不適用於本題需要輸出具體順序的需求。