C++ 圖論應用系列六：活動網路——AOV 拓撲排序與 AOE 關鍵路徑完整實作

前言：專案管理的數學模型——有向無環圖

活動網路（Activity Network）將專案建模為**有向無環圖（DAG）**：

• AOV (Activity On Vertex)：頂點 = 活動，邊 = 前後依賴關係
• AOE (Activity On Edge)：邊 = 活動（帶持續時間），頂點 = 事件/里程碑

核心算法：**拓撲排序**（AOV 可行性驗證與執行順序）與 **關鍵路徑**（AOE 專案工期與瓶頸分析）。

一、統一活動網路框架：ActivityNetwork 類別

template 
class ActivityNetwork {
    Network>* G;  // 綁定鄰接表圖
    int N;  // 頂點數
    vector criticalActivities;  // 關鍵活動
    int* count;   // 入度陣列 (AOV) / 事件最早時間 (AOE)
    int* result;  // 拓撲序列 / 事件最晚時間
    const int* out;  // 輸出指標
    
    struct CriAct { int s, d; CriAct() {} CriAct(int src, int dst) : s(src), d(dst) {} };
    
public:
    ActivityNetwork(Network>* g) 
        : G(g), N(G->vNum()), out(result) {
        count = new int[N]; result = new int[N];
    }
    ~ActivityNetwork() { delete[] count; delete[] result; }
    
    // 核心算法入口...
};

友元聲明**：需訪問 LinkedList 私有成員 vertices[i].e，故宣告為友元。

二、初始化：計算入度 / 建立邊迭代器宏

#define ITERATOR list::Edge>::iterator
#define BEGIN(i) G->data.vertices[i].e->begin()
#define END(i) G->data.vertices[i].e->end()

void initialize() {
    fill_n(count, N, 0);
    for (int i = 0; i < N; ++i)
        for (ITERATOR iter = BEGIN(i); iter != END(i); ++iter)
            ++count[iter->vID];  // 統計入度
    out = result;
}

三、AOV 拓撲排序：Kahn 算法 (BFS 版)

bool topologicalSort() {
    initialize();
    queue q;
    for (int i = 0; i < N; ++i)
        if (count[i] == 0) q.push(i);  // 入度 0 入隊
    
    int sortedCount = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        result[sortedCount++] = u;  // 輸出拓撲序列
        
        for (ITERATOR iter = BEGIN(u); iter != END(u); ++iter) {
            int v = iter->vID;
            if (--count[v] == 0) q.push(v);  // 入度歸零入隊
        }
    }
    
    if (sortedCount != N) {  // 存在環
        cout << "Cycle detected! Not a valid AOV network." << endl;
        return false;
    }
    out = result;
    return true;
}

意義**：

• 輸出合法執行順序（平行任務可交換順序）
• 檢測循環依賴（專案規劃錯誤）
• 平行化調度基礎：同層級任務可並行

四、AOE 關鍵路徑：雙向動態規劃

關鍵概念

算法流程

1. 拓撲排序**：獲取執行順序 result[]
2. 正向計算 ve[]**：按拓撲序，ve[j] = max(ve[j], ve[i] + weight(i,j))
3. 反向計算 vl[]**：按逆拓撲序，vl[i] = min(vl[i], vl[j] - weight(i,j))，初始 vl[sink] = ve[sink]
4. 識別關鍵活動**：slack = 0 的邊構成關鍵路徑

完整實作

void criticalPath() {
    if (!topologicalSort()) return;  // 必須是 DAG
    
    int* ve = new int[N];  // 最早時間
    int* vl = new int[N];  // 最晚時間
    fill_n(ve, N, 0);
    
    // 1. 正向：計算 ve
    for (int k = 0; k < N; ++k) {
        int u = result[k];
        for (ITERATOR iter = BEGIN(u); iter != END(u); ++iter) {
            int v = iter->vID;
            if (ve[u] + iter->cost > ve[v])
                ve[v] = ve[u] + iter->cost;
        }
    }
    
    // 2. 反向：計算 vl
    fill_n(vl, N, ve[result[N-1]]);  // 汇點最晚 = 最早
    for (int k = N-1; k >= 0; --k) {
        int u = result[k];
        for (ITERATOR iter = BEGIN(u); iter != END(u); ++iter) {
            int v = iter->vID;
            if (vl[v] - iter->cost < vl[u])
                vl[u] = vl[v] - iter->cost;
        }
    }
    
    // 3. 識別關鍵活動
    criticalActivities.clear();
    for (int u = 0; u < N; ++u) {
        for (ITERATOR iter = BEGIN(u); iter != END(u); ++iter) {
            int v = iter->vID;
            int e = ve[u];
            int l = vl[v] - iter->cost;
            if (e == l)  // 浮動時間為 0
                criticalActivities.emplace_back(u, v);
        }
    }
    
    delete[] ve; delete[] vl;
    out = result;  // 可輸出拓撲序列
}

五、工程應用場景

六、現代擴展：資源約束排程 (RCPSP)

標準 AOE 假設資源無限。現實中**資源有限**（機器、人員、預算），引入 **RCPSP (Resource-Constrained Project Scheduling Problem)**：

• NP-Hard 問題，需啟發式/元啟發式（遺傳算法、模擬退火、禁忌搜尋）
• 關鍵鏈專案管理 (CCPM) 緩衝管理理論
• Microsoft Project、Primavera P6 等商業軟體核心引擎

總結

活動網路將專案管理數學化：**AOV 拓撲排序解決「能不能做、怎麼做順序」，AOE 關鍵路徑解決「多久做完、哪裡不能延」**。掌握 ve/vl 雙向動態規劃與浮動時間計算，是專案管理軟體、編譯器優化、硬體時序分析的核心算法素養。圖論應用六部曲完結，從儲存到演算法，從無向到有向，從靜態到動態，構建完整圖算法工程視野。