演算法知識 - Topological Ordering 拓樸排序(時間複雜度 O(V+E))

Topological Ordering 拓樸排序 介紹

在有些程式問題，可能會有以下這些需求

• 我們需要做完 n 個任務，但有些任務有依賴需求，需要某個任務完成才可以做這個任務，請給出一份符合要求的任務清單
• 要幫學員排隊，但有些人必須排在某些人的後面，請給出一份符合要求的排隊順序

也就是對於一個序列，其中的某兩點具有先後關係，即是拓樸排序

Topological Ordering 限制

Topological Ordering 有些要求，如下

• 必須是有向圖
  如果是無向圖，不會有順序的概念。
• 不可以有環(cycle)
  如果有環，無法確定先後的關係，例如順時鐘或逆時鐘，則 1 這個數字的位置就不同。

Topological Ordering 實作與說明

在程式碼進行說明，相信會比較好理解些。

基本上此演算法類似於 BFS，如果有學過 BFS 一定會相當好懂。

定義名詞

• 紀錄關係
  a,b ，則 a 必須在 b 前面、c,d，則 c 必須在 d 前面，此時我們會稱 a,c 為前面節點、b,d 是後面節點。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 120
using namespace std;
int n, m, a, b;
int cnt[MAXN]; //記錄關係，以此節點為後面，而有多少節點在其前面
vector<int> root[MAXN], ans; 
//root 記錄關係，以此節點為前面，而另一節點就在後面 (vector.push_back)
//ans 答案序列，拓樸排序的序列

void topo(){

    for(int i = 0; i < m; i++){ //不斷輸入 
        cin >> a >> b; //輸入記錄關係，a 是前者 b 是後者
        root[a].push_back(b);  //記錄關係，記錄 a 有多少後面節點，並且記錄。
        cnt[b]++; //記錄有幾個前面節點，如果 b 是後面關係時。
    } 

    deque<int> q; //用來判斷有哪些節點現在已經可以直接被放到答案序列
    for(int i = 1; i <= n; i++){
        if(cnt[i] == 0) q.push_back(i); 
        //在記錄關係中，如果以此節點為後面，沒有節點在前面就加入 q
    }

    int now; //暫存 bfs(q) 當前的節點
    ans.clear(); //答案序列清空
    while(ans.size() != n){ //如果答案序列的長度跟題目給的長度一樣就跳出
        if(q.empty()) break; //如果沒有節點可以直接被放入答案序列就跳出
        now = q.front(); q.pop_front(); //把當前節點給 now
        ans.push_back(now); //將 now 放入答案序列
        for(auto it: root[now]){ //由於 now 節點被放入答案陣列，
        //之前的記錄關係就不須記錄，因為放到答案陣列就剩下的後面節點就必定在後面

            cnt[it]--; //將所有原本在記錄關係中後面的節點 -1，減少了一個記錄關係
            if(cnt[it] == 0) q.push_back(it); //如果都沒有記錄關係就可以放到 q
        }
    }
    if(ans.size() == n){ //如果答案序列跟 n 一樣，表示可以成功排出拓樸排序，就輸出答案
        for(int i = 0; i < ans.size(); i++) cout << ' ' << ans[i];
        cout << '\n';
    }
}

Topological Ordering 應用

點擊 tag Topological Ordering 就可以看到所有我寫過的應用題目

參考連結

師大演算法 - Topological Ordering

心得

想註解真的是一件很難的事情！我腦袋滿滿的想法就是講不出來…，是我的高職國文沒有學好嗎，感覺自己的詞彙量沒有很大，還需要再好好進步，讓自己對於國文的表達能力在更好些。

Topological Ordering 無註解程式碼

這裡則放置沒有註解的程式碼，如果讀者想要複製就從這裡進行複製吧！

int n, m, a, b;
int cnt[MAXN];
vector<int> root[MAXN], ans;

void topo(){
    deque<int> q;
    for(int i = 1; i <= n; i++){
        if(cnt[i] == 0) q.push_back(i);
    }

    int now;
    ans.clear();
    while(ans.size() != n){
        if(q.empty()) break;
        now = q.front(); q.pop_front();
        ans.push_back(now);
        for(auto it: root[now]){
            cnt[it]--;
            if(cnt[it] == 0) q.push_back(it);
        }
    }
    if(ans.size() == n){
        cout << ans[0];
        for(int i = 1; i < ans.size(); i++) cout << ' ' << ans[i];
        cout << '\n';
    }
}