有向無環圖拓撲排序：Kahn 算法 C++ 完整實現與工程應用

前言

拓撲排序是對有向無環圖 (DAG) 頂點的線性排序，使得對於任意邊 u → v，u 在 v 之前。廣泛應用於任務調度、編譯依賴、課程先修等場景。本文提供基於鄰接表與 Kahn 算法 (BFS 入度法) 的工程級 C++ 實現。

核心算法：Kahn 算法 (BFS 版)

1. 計算所有頂點入度
2. 將入度為 0 的頂點入隊
3. 重複：出隊頂點 u，輸出；遍歷 u 的出邊 u → v，v 入度 -1，若變 0 入隊
4. 若輸出頂點數 < 總頂點數，說明圖中有環

數據結構設計

struct GraphNode {
    int vertex;      // 頂點編號
    int inDegree;    // 入度
    int topNum;      // 拓撲序號
};

struct EdgeNode {
    int edge_id;     // 邊編號
    int src, dest;   // 起點、終點
    int weight;      // 權重
};

class Graph {
    int vertex_num, edge_num;
    vector> adj;      // 鄰接表
    vector nodes;         // 頂點信息
public:
    Graph(char* raw_edges[], int m); // 從原始數據構建
    vector topoSort();          // 返回拓撲序列
    void print();                    // 打印鄰接表
};

關鍵實現細節

圖構建：去重邊、保留最小權重

void Graph::addEdge(char* raw[], int idx) {
    // 解析: edge_id, src, dest, weight
    // 若 src→dest 已存在，保留 weight 較小者
    // 更新 nodes[dest].inDegree++
}

拓撲排序核心邏輯

vector Graph::topoSort() {
    vector result;
    queue q;
    
    // 初始入度為 0 的頂點入隊
    for (int i = 0; i < vertex_num; ++i)
        if (nodes[i].inDegree == 0) q.push(i);
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        result.push_back(u);
        
        for (auto& e : adj[u]) {
            int v = e.dest;
            if (--nodes[v].inDegree == 0)
                q.push(v);
        }
    }
    
    if (result.size() != vertex_num) 
        cerr << "圖中存在環，無法拓撲排序" << endl;
    return result;
}

測試用例與輸出

輸入格式：每行 edge_id, src, dest, weight

0,1,2,1
1,1,3,1
2,1,4,1
3,2,4,1
4,2,5,1
5,3,6,1
6,4,3,1
7,4,6,1
8,4,7,1
9,5,4,1
10,5,7,1
11,7,6,1

輸出：

拓撲排序結果: 1 2 4 3 5 7 6
鄰接表驗證:
1 --> 2(邊號:0,權重:1) --> 3(邊號:1,權重:1) --> 4(邊號:2,權重:1) --> NULL
2 --> 4(邊號:3,權重:1) --> 5(邊號:4,權重:1) --> NULL
...

工程級擴展建議

• 環檢測：返回 pair<bool, vector<int>> 區分有環/無環
• 字典序最小拓撲序：用 priority_queue<int, vector<int>, greater<int>> 替換隊列
• 並行任務調度：記錄每層寬度，對應可並行執行的任務組
• 動態圖增量更新：維護入度數組，新增邊時局部調整

總結

Kahn 算法以 O(V+E) 時間、O(V) 空間高效解決拓撲排序。工程實現關鍵在於：

1. 鄰接表高效存儲稀疏圖
2. 入度數組動態維護
3. 隊列管理零入度頂點集合
4. 邊去重與權重優化處理

完整代碼包含讀文件、構建圖、拓撲排序、釋放內存全流程，可直接集成到項目中。