【筆記】Topological Sort 拓撲排序

  • 【用途】有向無環圖(Directed Acyclic Graph, DAG)進行順序排序。
    • 圖形的「頂點」表示任務編號。
    • 圖形的「邊」表示一個任務是另一個任務的前置作業。
    • 拓撲排序即為一個有效的任務執行順序。
  • 【實作】
    • vector<int> g:每個頂點「出邊」連結的頂點。
    • in[ ]:紀錄每個頂點的in-degree(「入邊」數目)
    • queue<int> q:紀錄in-degree為零的頂點
    • vector<int> ans:紀錄有效的拓撲順序
    • 最後檢查ans的長度是否等於頂點的個數
  • 【時間複雜度】
    • O( V + E),其中V為圖的頂點個數,E是邊數。
  • 【範例】TIOJ 1092 . A.跳格子遊戲
  • 【更多練習】Codeforces 510C. Fox And Names
for (int i=0; i<m; i++){
    cin >> a >> b;
    //將頂點編號轉成zero-based
    a--;
    b--;
    g[a].push_back(b);
    in[b]++;
}

queue<int> q;
for (int i=0; i<n; i++){
    //找出「入邊」(in-degree)為零的頂點
    if (in[i] == 0) q.push(i);
}

vector<int> ans;
while (!q.empty()){
    int now = q.front();
    q.pop();
    ans.push_back(now);

    //遍歷子任務
    for (auto nxt: g[now]){
        in[nxt]--;
        if (in[nxt] == 0) q.push(nxt);
    }
}

分享本文 Share with friends