引言
在圖論中，拓撲排序（Topological Sorting）是一種重要的算法，主要用于解決有向無環圖（DAG）中的依賴關系問題。它在任務調度、編譯器的依賴解析、課程安排等領域有著廣泛的應用。本文將詳細介紹拓撲排序的背景、定義、原理、應用場景，并通過偽代碼和具體代碼實現幫助讀者深入理解。最后，我們將結合一道題目，講解如何使用拓撲排序解決實際問題。
背景知識
有向無環圖（DAG）
- 有向圖：由頂點和有向邊組成的圖，邊具有方向性。
- 無環圖：圖中不存在任何有向環路。
- 拓撲排序：只適用于有向無環圖（DAG），用于確定頂點的線性順序，使得對于每一條有向邊 $(u, v)$，頂點 $u$ 在頂點 $v$ 之前。
拓撲排序的應用場景
- 任務調度：確定任務的執行順序，確保依賴任務先完成。
- 編譯器：解析源代碼中的依賴關系，確定編譯順序。
- 課程安排：確定課程的選修順序，確保先修課程在前。
- 項目管理：確定任務的優先級和順序。
拓撲排序的定義
給定一個有向無環圖 $G = (V, E)$，拓撲排序是將圖中所有頂點排成一個線性序列，使得對于每一條有向邊 $(u, v)$，頂點 $u$ 在頂點 $v$ 之前。
示例
假設有以下有向圖：
1 -> 2 -> 3
1 -> 4
4 -> 3
一個合法的拓撲排序是：1, 2, 4, 3 或 1, 4, 2, 3。
拓撲排序的原理
拓撲排序的核心思想是通過不斷移除入度為 0 的頂點，并更新其鄰接頂點的入度，直到所有頂點都被移除或無法繼續移除。
算法步驟
- 初始化：
- 計算每個頂點的入度（即指向該頂點的邊的數量）。
- 將所有入度為 0 的頂點加入隊列。
- 處理隊列：
- 從隊列中取出一個頂點，將其加入拓撲排序結果。
- 遍歷該頂點的所有鄰接頂點，將其入度減 1。如果某個鄰接頂點的入度變為 0，則將其加入隊列。
- 結束條件：
- 如果所有頂點都被處理，則拓撲排序成功。
- 如果隊列為空但仍有未處理的頂點，則圖中存在環，拓撲排序失敗。
拓撲排序的偽代碼
function TopologicalSort(Graph):
// 初始化
in_degree = 計算每個頂點的入度
queue = 所有入度為 0 的頂點
result = 空列表
// 處理隊列
while queue 不為空:
u = queue.pop()
result.append(u)
for each v in u 的鄰接頂點:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.push(v)
// 檢查是否所有頂點都被處理
if result 的長度等于圖的頂點數:
return result
else:
return "圖中存在環，無法進行拓撲排序"
拓撲排序的代碼實現
示例1
ACWing 有向圖的拓撲序列
以下是拓撲排序的 C++ 實現，結合題目要求輸出任意一個合法的拓撲序列，如果不存在則輸出 -1。
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 7; // 定義最大頂點數和邊數
int n, m; // 頂點數和邊數
int in[maxn]; // 存儲每個頂點的入度
int h[maxn], ne[maxn], t[maxn], idx; // 鄰接表存儲圖
// 添加一條有向邊
void add(int u, int v) {
ne[++idx] = h[u];
h[u] = idx;
t[idx] = v;
}
// 拓撲排序函數
void topo() {
int cnt = 0; // 記錄已處理的頂點數
queue<int> q, ans; // q 用于 BFS，ans 用于存儲拓撲排序結果
// 將所有入度為 0 的頂點加入隊列
for (int i = 1; i <= n; i++) {
if (!in[i]) {
q.push(i);
cnt++;
ans.push(i);
}
}
// BFS 遍歷
while (!q.empty()) {
int cur = q.front();
q.pop();
// 遍歷當前頂點的所有鄰接頂點
for (int i = h[cur]; i != -1; i = ne[i]) {
int v = t[i];
in[v]--; // 鄰接頂點的入度減 1
if (!in[v]) { // 如果入度為 0，加入隊列
q.push(v);
cnt++;
ans.push(v);
}
}
}
// 判斷是否所有頂點都被處理
if (cnt != n) {
cout << -1; // 存在環，無法進行拓撲排序
} else {
// 輸出拓撲排序結果
while (!ans.empty()) {
cout << ans.front() << " ";
ans.pop();
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m; // 輸入頂點數和邊數
memset(h, -1, sizeof(h)); // 初始化鄰接表
// 輸入 m 條邊
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
in[y]++; // 更新入度
add(x, y); // 添加有向邊
}
topo(); // 調用拓撲排序函數
return 0;
}
代碼解析
1. 數據結構
- 鄰接表：使用數組
h、ne和t存儲圖。 - 入度數組：
in[i]表示頂點 $i$ 的入度。 - 隊列：用于 BFS 遍歷和存儲拓撲排序結果。
2. 拓撲排序函數
- 初始化：將所有入度為 0 的頂點加入隊列。
- BFS 遍歷：從隊列中取出頂點，更新其鄰接頂點的入度，并將入度為 0 的頂點加入隊列。
- 結果輸出：如果所有頂點都被處理，則輸出拓撲排序結果；否則輸出
-1。
3. 主函數
- 輸入處理：讀取頂點數、邊數以及邊的信息，并初始化鄰接表和入度數組。
- 調用拓撲排序：執行拓撲排序并輸出結果。
復雜度分析
時間復雜度
- 初始化：$O(n + m)$，其中 $n$ 是頂點數，$m$ 是邊數。
- BFS 遍歷：$O(n + m)$。
空間復雜度
- 鄰接表：$O(m)$。
- 隊列和入度數組：$O(n)$。
示例2
題目描述
John 的農場有 ( n ) 個雜務需要完成，每個雜務需要一定的時間，并且某些雜務必須在其他雜務完成后才能開始。我們需要計算完成所有雜務所需的最短時間。
輸入格式
- 第 1 行：一個整數 ( n )，表示雜務的數量。
- 第 2 到 ( n+1 ) 行：每行包含雜務的編號、完成時間以及其依賴的雜務列表（以 0 結束）。
輸出格式
- 一個整數，表示完成所有雜務所需的最短時間。
樣例輸入 #1
7
1 5 0
2 2 1 0
3 3 2 0
4 6 1 0
5 1 2 4 0
6 8 2 4 0
7 4 3 5 6 0
樣例輸出 #1
23
解題思路
1. 問題分析
- 每個雜務可以看作圖中的一個頂點。
- 雜務之間的依賴關系可以看作有向邊。
- 我們需要找到一種順序，使得所有雜務都能在其依賴的雜務完成后開始，并且總時間最短。
2. 拓撲排序的應用
- 拓撲排序可以用于解決有向無環圖（DAG）中的依賴關系問題。
- 通過拓撲排序，我們可以確定雜務的執行順序，并計算完成所有雜務的最短時間。
3. 算法設計
- 構建圖：
- 使用鄰接表存儲雜務之間的依賴關系。
- 記錄每個雜務的入度（即依賴的雜務數量）。
- 拓撲排序：
- 使用優先隊列（堆）選擇當前可以執行的雜務（入度為 0）。
- 更新雜務的完成時間，并將其依賴的雜務的入度減 1。
- 計算最短時間：
- 在拓撲排序過程中，記錄每個雜務的完成時間，并更新全局的最短時間。
- 在本題中，我們設計利用一個優先隊列，保證當前任務耗時最長的依賴任務在最后出隊，這樣才能保證時間更新的正確性。
我們結合示例進行分析：
7
1 5 0
2 2 1 0
3 3 2 0
4 6 1 0
5 1 2 4 0
6 8 2 4 0
7 4 3 5 6 0
代碼實現
以下是結合拓撲排序的 C++ 實現：
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 1e4 + 7; // 定義最大雜務數
int n; // 雜務數量
int in[maxn]; // 存儲每個雜務的入度
int times[maxn]; // 存儲每個雜務的完成時間
int h[maxn * 100], ne[maxn * 100], t[maxn * 100], idx; // 鄰接表存儲圖
// 添加一條有向邊
void add(int u, int v) {
ne[++idx] = h[u];
h[u] = idx;
t[idx] = v;
}
// 拓撲排序函數
void topo() {
int mx = 0; // 記錄全局的最短時間
priority_queue<pair<int, int>> q; // 優先隊列，存儲 (負完成時間, 雜務編號)
// 將所有入度為 0 的雜務加入隊列
for (int i = 1; i <= n; i++) {
if (!in[i]) {
q.push({-times[i], i});
}
}
// BFS 遍歷
while (!q.empty()) {
auto cur = q.top();
q.pop();
int cur_time = -cur.first; // 當前雜務的完成時間
int u = cur.second; // 當前雜務的編號
//最短完成時間但是取max的原因是需要等待耗時最長的依賴完成才能開始任務
mx = max(mx, cur_time); // 更新全局的最短時間
// 遍歷當前雜務的所有依賴雜務
for (int i = h[u]; i != -1; i = ne[i]) {
int v = t[i];
in[v]--; // 依賴雜務的入度減 1
if (!in[v]) {
// 如果依賴雜務的入度為 0，將其加入隊列
q.push({-(cur_time + times[v]), v});
}
}
}
// 輸出全局的最短時間
cout << mx;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n; // 輸入雜務數量
memset(h, -1, sizeof(h)); // 初始化鄰接表
// 輸入每個雜務的信息
for (int i = 1; i <= n; i++) {
int id;
cin >> id;
cin >> times[id]; // 輸入雜務的完成時間
int pre;
cin >> pre;
while (pre) {
in[id]++; // 更新雜務的入度
add(pre, id); // 添加依賴關系
cin >> pre;
}
}
topo(); // 調用拓撲排序函數
return 0;
}
代碼解析
1. 數據結構
- 鄰接表：使用數組
h、ne和t存儲雜務之間的依賴關系。 - 入度數組：
in[i]表示雜務 ( i ) 的入度（即依賴的雜務數量）。 - 完成時間數組：
times[i]表示雜務 ( i ) 的完成時間。 - 優先隊列：用于選擇當前可以執行的雜務。
2. 拓撲排序函數
- 初始化：將所有入度為 0 的雜務加入優先隊列。
- BFS 遍歷：
- 從隊列中取出雜務，更新其完成時間。
- 遍歷其依賴的雜務，更新其入度。
- 如果某個依賴雜務的入度為 0，則將其加入隊列。
- 結果輸出：輸出全局的最短時間。
3. 主函數
- 輸入處理：讀取雜務數量、完成時間以及依賴關系，并初始化鄰接表和入度數組。
- 調用拓撲排序：執行拓撲排序并輸出結果。
總結
拓撲排序是解決有向無環圖中依賴關系問題的有效算法。通過本文的介紹，讀者可以掌握拓撲排序的定義、原理、實現方法以及應用場景。結合代碼實現和題目講解，希望讀者能夠深入理解拓撲排序，并在實際問題中靈活運用。
如果你對拓撲排序或其他圖論算法有更多疑問，歡迎在評論區留言討論！
浙公網安備 33010602011771號