14.3 拓撲排序

拓撲排序（topological sort）是一種常見的算法，用於對有向無環圖（DAG）進行排序。給定 DAG 中的 $N$ 個節點，我們需要將它們排序成一個線性序列；如果節點 $i$ 指向節點 $j$，則排序結果中 $i$ 必須在 $j$ 之前。拓撲排序的結果並不唯一，只要滿足以上條件即可。

210. Course Schedule II

題目描述

給定 $N$ 門課程以及它們的前置必修課，找出可以一次性完成所有課程的修課順序。

輸入輸出範例

輸入是一個正整數，表示課程數量，以及一個二維陣列，表示所有的有向邊（例如 [1,0] 表示課程 1 必須在課程 0 之後修完）。輸出是一個一維陣列，表示拓撲排序的結果。

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3]

在這個例子中，另一種可行的順序是 [0,2,1,3]。

題解

我們可以先建立一個鄰接矩陣來表示圖，方便進行直接查找。這裡注意，我們將所有的邊進行反向處理，使得如果課程 $i$ 指向課程 $j$，表示課程 $i$ 必須在課程 $j$ 之前完成。這樣處理更符合我們對前置課程的直觀理解。

拓撲排序可以看作是廣度優先搜索（BFS）的一種特殊情況：

1. 遍歷所有節點，將入度為 $0$ 的節點（即無前置課程要求的節點）加入隊列。
2. 處理隊列中的節點：
   • 將當前節點加入排序結果中。
   • 將當前節點指向的所有節點的入度減少 $1$。
   • 如果某個節點的入度變為 $0$，將該節點加入隊列。
3. 當隊列處理完畢後，若所有節點均已排序，則完成拓撲排序；否則，若圖中存在環，則無法完成所有課程。

C++

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph(numCourses, vector<int>());
    vector<int> indegree(numCourses, 0), schedule;
    for (const auto& pr : prerequisites) {
        graph[pr[1]].push_back(pr[0]);
        ++indegree[pr[0]];
    }
    queue<int> q;
    for (int i = 0; i < indegree.size(); ++i) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        schedule.push_back(u);
        for (int v : graph[u]) {
            --indegree[v];
            if (indegree[v] == 0) {
                q.push(v);
            }
        }
    }
    for (int i = 0; i < indegree.size(); ++i) {
        if (indegree[i] != 0) {
            return vector<int>();
        }
    }
    return schedule;
}

Python

def findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    graph = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    schedule = []

    for pr_from, pr_to in prerequisites:
        graph[pr_to].append(pr_from)
        indegree[pr_from] += 1

    q = collections.deque([i for i, deg in enumerate(indegree) if deg == 0])

    while len(q) > 0:
        u = q.popleft()
        schedule.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                q.append(v)

    return schedule if all(deg == 0 for deg in indegree) else []