LeetCode程式設計訓練 - 拓撲排序(Topological Sort)
摘要：
拓撲排序基礎
拓撲排序用於解決有向無環圖(DAG,Directed Acyclic Graph)按依賴關係排線性序列問題，直白地說解決這樣的問題：有一組資料，其中一些資料依賴其他，問能否按依賴關係排序(被依賴的排在前面)，或給出排序結果。
最常用解決拓撲排序問題的方法是Kah...
拓撲排序基礎
拓撲排序用於解決有向無環圖(DAG,Directed Acyclic Graph)按依賴關係排線性序列問題，直白地說解決這樣的問題：有一組資料，其中一些資料依賴其他，問能否按依賴關係排序(被依賴的排在前面)，或給出排序結果。
最常用解決拓撲排序問題的方法是Kahn演算法 ，步驟可以概括為：
1. 根據依賴關係，構建鄰接矩陣或鄰接表、入度陣列 2. 取入度為0的資料(即不依賴其他資料的資料)，根據鄰接矩陣/鄰接表依次減小依賴其的資料的入度 3. 判斷減小後是否有新的入度為0的資料，繼續進行第2步 4. 直到所有資料入度為0、得到拓撲排序序列，或返回失敗(存在環形依賴)
其中2、3兩個步驟取入度為0資料、減小依賴其的資料的入度，過程像樹的寬度優先搜尋，用到類似BFS方法；以上過程用偽程式碼表示如下：
L ← Empty list that will contain the sorted elements S ← Set of all nodes with no incoming edge while S is non-empty do remove a node n from S add n to tail of L for each node m with an edge e from n to m do remove edge e from the graph if m has no other incoming edges then insert m into S if graph has edges then return error(graph has at least one cycle) else return L(a topologically sorted order)
下面看具體例子 207. Course Schedule (有n個課程，課程間有依賴關係，問能否完成所有課程)：
//207. Course Schedule
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
//構建鄰接矩陣、入度陣列
vector<vector<int>> adj(numCourses);
vector<int> indegree(numCourses,0);
for(auto x:prerequisites){
adj[x.second].push_back(x.first);
indegree[x.first]++;
}
//類似BFS
queue<int> q;
for(int i=0;i<numCourses;i++)
if(indegree[i]==0) q.push(i);
while(!q.empty()){
int cur=q.front();
q.pop();
numCourses--;
for(auto next:adj[cur])
if(--indegree[next]==0) q.push(next);//新入度為0的先處理，這與正統BFS有區別
}
//判斷最後所有資料入度為0
return numCourses==0;
}
以上用到鄰接矩陣(adjacency matrix)表示依賴關係，時間複雜度為O(V^2)，其中V為資料個數。視覺化過程：這裡