拓墣排序

簡介

拓墣排序 (Topological Sorting) 是一種有向圖上的演算法，最簡單的應用就是處理有順序關係的任務，不過這個算法其實還可以搭配之後的 動態規劃 來達到更進階的應用。

比如說，一小部分的 C++ 學習路程圖可能長這樣，你需要先學會環境建置才能學習輸入輸出，你需要先學會變數和幾基本運算才學的會回圈。拓撲排序就可以做到幫你把這些點做排序，建立一個學習順序，達到學習每個知識點之前都把需要先學的學會。

不過從上面那個例子應該可以感受到，如果圖中出現環就不可能做出拓撲排序。

實作方式

最常見的實作方式應該就是 Kahn Algorithm，這個演算法的實作其實很像 BFS，首先要把 in degree 為 0 的節點加入 queue，然後開始做 BFS，每造訪一個點就把該點指向的節點的 in degree 都減一，如果指向的點 in degree 為 0 就加入 queue，這個過程中拜訪節點的順序就是拓墣排序的順序！

vector<int> res; // 儲存結果
queue<int> q;

// 先把 in degree 為零的點都加入
for (int i = 1; i <= n; i++) {
    if (in[i] == 0) {
        q.push(i);
    }
}

while (!q.empty()) {
    int v = q.front();
    q.pop();
    // 把目前拜訪到的節點加入 res 陣列
    res.push_back(v);
    for (auto u : g[v]) {
        --in[u]; // 減少 u 的 in degree
        if (in[u] == 0) {
            q.push(u);
        }
    }
}

// 如果拜訪過的節點總數等於全部的節點就合法
if (res.size() == n) {
    for (auto i : L) cout << i << ' ';
    return true;
// 否則如果有環就不會拜訪到所有節點
} else {
    return false;
}

DFS

其實還有另一種比較不主流的作法，其實我們可以直接透過 DFS 就獲得拓墣排序！

不過在這之前，讓我們先更仔細的剖析一下 DFS 在做的事情。首先我們可以把 DFS 的過程分成四個部分：

void dfs(int v) {
    // 第 1 部分
    for (auto u : g[v]) {
        // 第 2 部分
        dfs(u);
        // 第 3 部分
    }
    // 第 4 部分
}

這些部分對應到遞迴樹上的話會長這樣，紅色是第一部分，藍色是第二部分，數字是執行的順序（第二和第三部分暫時不考慮）：

可以注意到，我們只要對每個節點紀錄「第四部分執行的順序」倒過來就是拓墣排序了，聽起來可能有點抽象，不過相信你看了下面的程式碼就會懂了：

void dfs(int v) {
    for (auto u : g[v]) {
        dfs(u);
    }
    ans.push(v);
}

int main() {
    // 執行 DFS
    dfs(1);
    // 翻轉陣列
    reverse(ans.begin(), ans.end());
    // 輸出結果
    for (auto e : ans) cout << e << " ";
}

拓墣排序是一個非常重要的概念，除了當成其他進階圖論演算法的基礎外，類似的概念 APCS 也在歷屆中考過了至少兩次。