Topological-Sorting（拓樸排序）

拓樸排序是 只有祖先都被走訪過的節點 才能被走訪
通常會在有向圖中的邊，用來陳述 A, B 的優先性
也就是當 A → B 時，代表 A 先被走訪後才能走訪 B

要點

觀念

此演算法需要
一維陣列：儲存某節點的未訪問祖先數量
二維陣列：儲存圖（鄰接串列）
佇列：儲存祖先已走訪完畢的節點（用佇列保持其順序性）

先找到沒有父節點的節點作為起始節點 (x) 將其放入佇列中
對所有 x → ? 的 ? 節點，將其一維陣列減 1
同時檢查，若 ? 節點的祖先已全部走訪完畢，則將 ? 放入佇列中

本文默認輸入的有向圖圍為單連通
若想要檢查該圖是否存在環，可以檢查拓樸排序的輸出有無包含所有節點

實作

宣告陣列

一維陣列 (w)
二維陣列 (g)

1
2
3
// n 為節點數量
vector<vector<int>> g(n);
vector<int> w(n, 0);

路徑數量

圖以鄰接串列的方式儲存
設某節點的未走訪父節點為該節點的權重

1
2
3
4
5
6
// m 為路徑數量
while (m--) {
    cin >> a >> b;
    g[a].push_back(b);
    w[b]++;
}

排序

先創建一個佇列為 q

1
queue<int> q;

利用 for 迴圈尋找沒有父節點的初始節點，將其放入佇列

1
for (int i = 0; i < n; i++) if (!w[i]) q.push(i);

取出最前面的元素，並且將所有與該元素單向連通的節點權重減 1
檢查該連通的節點權重減 1 後為 0，將其放入佇列
利用 while 迴圈直到佇列內沒有元素為止

1
2
3
4
5
while (q.size()) {
    cout << q.front() << ' ';
    for (auto i : g[q.front()]) if (!(--w[i])) q.push(i);
    q.pop();
}

範例

題目：UVA 10305

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

int main() { ios::sync_with_stdio(0); cin.tie(0);
    int n, m, a, b;
    while (cin >> n >> m && (n || m)) {
        vector<vector<int>> v(n);
        vector<int> w(n, 0), ans;
        
        while (m--) {
            cin >> a >> b;
            v[--a].push_back(--b);
            w[b]++;
        }

        queue<int> q;
        for (int i = 0; i < n; i++) if (!w[i]) q.push(i);
        
        while (q.size()) {
            cout << q.front()+1 << ' ';
            for (auto i : v[q.front()]) if (!(--w[i])) q.push(i);
            q.pop();
        }

        cout << '\n';
    }
}