跳转至

拓撲排序

定義

拓撲排序的英文名是 Topological sorting。

拓撲排序要解決的問題是給一個有向無環圖的所有節點排序。

我們可以拿大學每學期排課的例子來描述這個過程，比如學習大學課程中有：「程序設計」，「算法語言」，「高等數學」，「離散數學」，「編譯技術」，「普通物理」，「數據結構」，「數據庫系統」等。按照例子中的排課，當我們想要學習「數據結構」的時候，就必須先學會「離散數學」，學習完這門課後就獲得了學習「編譯技術」的前置條件。當然，「編譯技術」還有一個更加前的課程「算法語言」。這些課程就相當於幾個頂點 \(u\), 頂點之間的有向邊 \((u,v)\) 就相當於學習課程的順序。教務處安排這些課程，使得在邏輯關係符合的情況下排出課表，就是拓撲排序的過程。

topo

但是如果某一天排課的老師打瞌睡了，説想要學習 數據結構，還得先學 操作系統，而 操作系統 的前置課程又是 數據結構，那麼到底應該先學哪一個（不考慮同時學習的情況）？在這裏，數據結構 和 操作系統 間就出現了一個環，顯然同學們現在沒辦法弄清楚自己需要先學什麼了，也就沒辦法進行拓撲排序了。因為如果有向圖中存在環路，那麼我們就沒辦法進行拓撲排序。

因此我們可以説 在一個 DAG（有向無環圖） 中，我們將圖中的頂點以線性方式進行排序，使得對於任何的頂點 \(u\) 到 \(v\) 的有向邊 \((u,v)\), 都可以有 \(u\) 在 \(v\) 的前面。

還有給定一個 DAG，如果從 \(i\) 到 \(j\) 有邊，則認為 \(j\) 依賴於 \(i\)。如果 \(i\) 到 \(j\) 有路徑（\(i\) 可達 \(j\)），則稱 \(j\) 間接依賴於 \(i\)。

拓撲排序的目標是將所有節點排序，使得排在前面的節點不能依賴於排在後面的節點。

AOV 網

日常生活中，一項大的工程可以看作是由若干個子工程組成的集合，這些子工程之間必定存在一定的先後順序，即某些子工程必須在其他的一些子工程完成後才能開始。

我們用有向圖來表現子工程之間的先後關係，子工程之間的先後關係為有向邊，這種有向圖稱為頂點活動網絡，即 AOV 網 (Activity On Vertex Network)。一個 AOV 網必定是一個有向無環圖，即不帶有迴路。與 DAG 不同的是，AOV 的活動都表示在邊上。（上面的例圖即為一個 AOV 網）

在 AOV 網中，頂點表示活動，弧表示活動間的優先關係。AOV 網中不應該出現環，這樣就能夠找到一個頂點序列，使得每個頂點代表的活動的前驅活動都排在該頂點的前面，這樣的序列稱為拓撲序列（一個 AOV 網的拓撲序列不是唯一的），由 AOV 網構造拓撲序列的過程稱為拓撲排序。因此，拓撲排序也可以解釋為將 AOV 網中所有活動排成一個序列，使得每個活動的前驅活動都排在該活動的前面（一個 AOV 網中的拓撲排序也不是唯一的）。

  • 前驅活動：有向邊起點的活動稱為終點的前驅活動（只有當一個活動的前驅全部都完成後，這個活動才能進行）。

  • 後繼活動：有向邊終點的活動稱為起點的後繼活動。

檢測 AOV 網中是否帶環的方式是構造拓撲序列，看是否包含所有頂點。

構造拓撲序列步驟

  1. 從圖中選擇一個入度為零的點。
  2. 輸出該頂點，從圖中刪除此頂點及其所有的出邊。

重複上面兩步，直到所有頂點都輸出，拓撲排序完成，或者圖中不存在入度為零的點，此時説明圖是有環圖，拓撲排序無法完成，陷入死鎖。

關鍵路徑和 AOE 網

與 AOV 網對應的是 AOE 網（Activity On Edge Network) 即邊表示活動的網。AOE 網是一個帶權的有向無環圖，其中，頂點表示事件，弧表示活動持續的時間。通常，AOE 網可以用來估算工程的完成時間。AOE 網應該是無環的，且存在唯一入度為零的起始頂點（源點），以及唯一出度為零的完成頂點（匯點）。

topo

AOE 網中的有些活動是可以並行進行的，所以完成整個工程的最短時間是從開始點到完成點的最長活動路徑長度（這裏所説的路徑長度是指路徑上各活動的持續時間之和，即弧的權值之和，不是路徑上弧的數目）。因為一項工程需要完成所有工程內的活動，所以最長的活動路徑也是關鍵路徑，它決定工程完成的總時間。

AOE 網的相關基本概念

  • 活動：AOE 網中，弧表示活動。弧的權值表示活動持續的時間，活動在事件被觸發後開始。

  • 事件：AOE 網中，頂點表示事件，事件能被觸發。

  • 弧（活動）\(a_j\) 的最早開始時間：初始點到該弧起點的最長路徑長度，記為 \(e(j)\)。

  • 弧（活動）\(a_j\) 的最遲開始時間：在不推遲整個工期的前提下，工程達到弧起點所表示的狀態最晚能容忍的時間，記為 \(l(j)\)。

  • 頂點（事件）\(v_j\) 的最早發生時間：初始點到該頂點的最長路徑長度，記為 \(ve(j)\)，它決定了以該頂點開始的活動的最早發生時間，所以 \(ve(j)=e(j)\)。

  • 頂點（事件）\(v_j\) 的最遲發生時間：在不推遲整個工期的前提下，工程達到頂點所表示的狀態最晚能容忍的時間，記為 \(vl(j)\)，它決定了所有以該狀態結束的活動的最遲發生時間，所以 \(l(j)=vl(j)-dul(aj)\)。

  • 關鍵路徑：AOE 網中從源點到匯點的最長路徑的長度。

  • 關鍵活動：關鍵路徑上的活動，最早開始時間和最遲開始時間相等。

最早和最遲發生時間的遞推關係

\[ ve(j) = \max\{ve(k) + dut(\langle k,j\rangle)\},\quad \langle k,j\rangle \in T,2\le j\le n \]
\[ vl(j) = \min\{vl(k) - dut(\langle j,k\rangle)\},\quad \langle j,k\rangle \in S,1\le j\le n-1 \]

按拓撲順序求，最早是從前往後，前驅頂點的最早開始時間與邊的權重之和最大者，最遲是從後往前，後繼頂點的最遲開始時間與邊的權重之差的最小者。

關鍵路徑算法

  1. 輸入 \(e\) 條弧 \((j,k)\)，建立 AOE 網；

  2. 從源點 \(v_0\) 出發，令 \(ve[0] = 0\), 按照拓撲排序求其餘各個頂點的最早發生時間 \(ve[i],~(i \le i \le n-1)\)。如果得到的拓撲有序序列中頂點的個數小於網中的頂點數 \(n\)，則説明網中存在環，不能求關鍵路徑，算法終止；否則執行步驟 3；

  3. 從匯點 \(v_n\) 出發，令 \(vl[n-1] = ve[n-1]\)，按照逆拓撲有序求其餘各頂點的最遲發生時間 \(vl[i],~(n-2 \ge i \ge 2)\);

  4. 根據各頂點的 \(ve\) 和 \(vl\) 值，求每條弧 \(s\) 的最早開始時間 \(e(s)\) 和最遲開始時間 \(l(s)\)。若某條弧滿足條件 \(e(s) = l(s)\), 則為關鍵活動。

Kahn 算法

過程

初始狀態下，集合 \(S\) 裝着所有入度為 \(0\) 的點，\(L\) 是一個空列表。

每次從 \(S\) 中取出一個點 \(u\)（可以隨便取）放入 \(L\), 然後將 \(u\) 的所有邊 \((u, v_1), (u, v_2), (u, v_3) \cdots\) 刪除。對於邊 \((u, v)\)，若將該邊刪除後點 \(v\) 的入度變為 \(0\)，則將 \(v\) 放入 \(S\) 中。

不斷重複以上過程，直到集合 \(S\) 為空。檢查圖中是否存在任何邊，如果有，那麼這個圖一定有環路，否則返回 \(L\)，\(L\) 中頂點的順序就是構造拓撲序列的結果。

首先看來自 Wikipedia 的偽代碼

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is not empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else
    return L (a topologically sorted order)

代碼的核心是維持一個入度為 0 的頂點的集合。

可以參考該圖

topo

對其排序的結果就是：2 -> 8 -> 0 -> 3 -> 7 -> 1 -> 5 -> 6 -> 9 -> 4 -> 11 -> 10 -> 12

時間複雜度

假設這個圖 \(G = (V, E)\) 在初始化入度為 \(0\) 的集合 \(S\) 的時候就需要遍歷整個圖，並檢查每一條邊，因而有 \(O(E+V)\) 的複雜度。然後對該集合進行操作，顯然也是需要 \(O(E+V)\) 的時間複雜度。

因而總的時間複雜度就有 \(O(E+V)\)

實現

 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
int n, m;
vector<int> G[MAXN];
int in[MAXN];  // 存儲每個結點的入度

bool toposort() {
  vector<int> L;
  queue<int> S;
  for (int i = 1; i <= n; i++)
    if (in[i] == 0) S.push(i);
  while (!S.empty()) {
    int u = S.front();
    S.pop();
    L.push_back(u);
    for (auto v : G[u]) {
      if (--in[v] == 0) {
        S.push(v);
      }
    }
  }
  if (L.size() == n) {
    for (auto i : L) cout << i << ' ';
    return true;
  } else {
    return false;
  }
}

DFS 算法

實現

 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
28
29
30
31
32
33
34
35
36
using Graph = vector<vector<int>>;  // 鄰接表

struct TopoSort {
  enum class Status : uint8_t { to_visit, visiting, visited };

  const Graph& graph;
  const int n;
  vector<Status> status;
  vector<int> order;
  vector<int>::reverse_iterator it;

  TopoSort(const Graph& graph)
      : graph(graph),
        n(graph.size()),
        status(n, Status::to_visit),
        order(n),
        it(order.rbegin()) {}

  bool sort() {
    for (int i = 0; i < n; ++i) {
      if (status[i] == Status::to_visit && !dfs(i)) return false;
    }
    return true;
  }

  bool dfs(const int u) {
    status[u] = Status::visiting;
    for (const int v : graph[u]) {
      if (status[v] == Status::visiting) return false;
      if (status[v] == Status::to_visit && !dfs(v)) return false;
    }
    status[u] = Status::visited;
    *it++ = u;
    return true;
  }
};

 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
28
29
30
from enum import Enum, auto


class Status(Enum):
    to_visit = auto()
    visiting = auto()
    visited = auto()


def topo_sort(graph: list[list[int]]) -> list[int] | None:
    n = len(graph)
    status = [Status.to_visit] * n
    order = []

    def dfs(u: int) -> bool:
        status[u] = Status.visiting
        for v in graph[u]:
            if status[v] == Status.visiting:
                return False
            if status[v] == Status.to_visit and not dfs(v):
                return False
        status[u] = Status.visited
        order.append(u)
        return True

    for i in range(n):
        if status[i] == Status.to_visit and not dfs(i):
            return None

    return order[::-1]

時間複雜度：\(O(E+V)\) 空間複雜度：\(O(V)\)

合理性證明

考慮一個圖，刪掉某個入度為 \(0\) 的節點之後，如果新圖可以拓撲排序，那麼原圖一定也可以。反過來，如果原圖可以拓撲排序，那麼刪掉後也可以。

應用

拓撲排序可以判斷圖中是否有環，還可以用來判斷圖是否是一條鏈。拓撲排序可以用來求 AOE 網中的關鍵路徑，估算工程完成的最短時間。

求字典序最大/最小的拓撲排序

將 Kahn 算法中的隊列替換成最大堆/最小堆實現的優先隊列即可，此時總的時間複雜度為 \(O(E+V \log{V})\)。

習題

CF 1385E：需要通過拓撲排序構造。

Luogu P1347: 拓撲排序模板。

參考

  1. 離散數學及其應用。ISBN:9787111555391
  2. https://blog.csdn.net/dm_vincent/article/details/7714519
  3. Topological sorting,https://en.wikipedia.org/w/index.php?title=Topological_sorting&oldid=854351542
  4. https://blog.csdn.net/time_money/article/details/109857779
  5. https://zhuanlan.zhihu.com/p/164751109
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用