貪婪算法經典應用：拓撲排序原理、C++ 實現與複雜度分析

貪婪算法經典應用：拓撲排序原理、C++ 實現與複雜度分析

拓撲排序是有向無環圖 (DAG) 頂點的一種線性排序，使得對於任意邊 (u,v)，u 總排在 v 之前。它是任務調度、編譯依賴解析、課程先修關係等場景的核心算法，本質是貪婪策略的應用。

問題建模：AOV 網 (Activity On Vertex)

• 頂點 = 任務
• 有向邊 (i,j) = 任務 i 必須在任務 j 之前完成
• 拓撲序列 = 滿足所有先後約束的任務執行順序

貪婪選擇準則

「每步從剩餘頂點中選入度為 0 的頂點 (無前驅依賴) 加入序列。」

若某步無入度為 0 的頂點可選，說明圖中存在環，**拓撲序列不存在**。

算法演示 (圖 1-4 六任務示例)

初始入度：[0,0,1,3,1,3] (1-based)
候選棧：{1,2}
可能序列 (非唯一)：2→5→1→3→4→6, 1→2→3→4→5→6, 2→1→5→3→4→6 等。

正確性證明雙重保障

1. 算法不失敗 ⇒ 生成的序列是拓撲序列：直接由貪婪準則保證 (每加入頂點無未滿足前驅)。
2. 算法失敗 ⇒ 圖含環 ⇒ 不存在拓撲序列：若失敗，剩餘子圖所有頂點入度 ≥ 1，必存在環。環中任務互相前驅，不可能線性排序。

高效數據結構：Kahn 算法 (BFS + 入度表 + 棧/隊列)

• indeg[v]：頂點 v 當前入度
• 初始化：掃描所有邊統計入度 O(n+e)
• 將入度 0 頂點壓入棧/隊列
• 循環彈出頂點 → 輸出 → 遍歷其出邊遞減目標入度 → 入度變 0 者入棧
• 最終輸出長度 n 即成功，否則有環

C++ 實現 (鄰接表版，O(n+e))

#include 
#include 

struct Network {
    int n;                              // 頂點數 (1..n)
    std::vector> adj;  // 鄰接表 adj[u] = {v1,v2,...}
    
    Network(int n_) : n(n_), adj(n_ + 1) {}
    void addEdge(int u, int v) { adj[u].push_back(v); }
    
    // 拓撲排序，成功返回 true 並將序列存入 topo (0-based 索引)
    bool Topological(std::vector &topo) {
        topo.clear();
        std::vector indeg(n + 1, 0);
        
        // 統計入度
        for (int u = 1; u <= n; ++u)
            for (int v : adj[u])
                ++indeg[v];
        
        // 初始零入度頂點入棧
        std::stack st;
        for (int i = 1; i <= n; ++i)
            if (indeg[i] == 0) st.push(i);
        
        // 貪婪構造序列
        while (!st.empty()) {
            int u = st.top(); st.pop();
            topo.push_back(u);
            for (int v : adj[u]) {
                if (--indeg[v] == 0) st.push(v);
            }
        }
        return topo.size() == n;
    }
};

複雜度分析

稀疏圖 (e ≪ n²) 必用鄰接表。

關鍵應用場景

• 編譯系統：源文件依賴關係 → 編譯順序 (Make/CMake 內核邏輯)
• 任務調度：CI/CD 流水線、專案管理 (PERT/CPM)
• 課程規劃：大學選課系統先修檢查
• 軟件包管理：npm/apt/pip 依賴解析安裝順序
• 數據庫：事務調度、外鍵約束檢查順序

變體與優化

• 字典序最小拓撲序列：棧改用 priority_queue (小根堆)
• 並行拓撲排序：識別可並行執行的任務層級 (層次遍歷)
• 動態圖增量維護：邊插入/刪除時局部更新入度與序列

拓撲排序是圖論中最實用的算法之一，掌握其貪婪本質、Kahn 算法實現與 O(n+e) 複雜度分析，是解決一切「有依賴順序的調度問題」的鑰匙。