拓撲排序

拓撲排序的原理及其實作

LeetCode 207. Course Schedule

LeetCode discuss

Kahn算法

1. 從有向圖中選取一個沒有前驅(即入度為0)的頂點，并輸出之;
2. 從有向圖中删去此頂點以及所有以它為尾的弧;
3. 如果最後還有頂點，則圖中有環

bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
    vector<vector<int>> matrix(numCourses); //鄰接表
    vector<int> indegree(numCourses);  //點的入度
    for (auto it : prerequisites) {
        matrix[it.second].push_back(it.first);
        indegree[it.first]++;
    }
    queue<int> q;
    for (int i = ; i < numCourses; ++i) {
        if (indegree[i] == ) q.push(i);   //入度為0的頂點加入
    }
    int removed_nodes = ;
    while (!q.empty()) {
        int course = q.front();
        q.pop();
        removed_nodes++;
        for (auto i : matrix[course]) {
            if (--indegree[i] == )
                q.push(i);
        }
    }
    return removed_nodes == numCourses; //是否有環        
}
           

DFS

Kahn算法考慮的是入度，DFS考慮出度。從0出度遞推

L ← Empty list that will contain the sorted nodes
S ← Set of all nodes with no outgoing edges
for each node n in S do
    visit(n) 
function visit(node n)
    if n has not been visited yet then
        mark n as visited
        for each node m with an edgefrom m to ndo
            visit(m)
        add n to L