拓撲排序與關鍵路徑演算法：AOV/AOE 網完整實作與專案排程應用

應用場景

• 拓撲排序：課程先修規劃、編譯依賴順序、任務排程、流程依賴分析
• 關鍵路徑：專案工期最短時間、關鍵任務識別、資源優化配置

核心圖模型

拓撲排序演算法 (Kahn 算法)

步驟

1. 計算所有頂點入度
2. 將入度為 0 的頂點入堆疊/佇列
3. 重複：彈出頂點 → 輸出 → 刪除其出邊 → 更新鄰接點入度 → 入度變 0 者入堆疊
4. 若輸出頂點數 < 總頂點數 → 存在環路 → 無拓撲序

程式碼實作

#define MAXVEX 100

typedef struct EdgeNode {
    int adjvex;
    int weight;
    struct EdgeNode *next;
} EdgeNode;

typedef struct VertexNode {
    int in;              // 入度
    int data;
    EdgeNode *firstedge;
} VertexNode, AdjList[MAXVEX];

typedef struct {
    AdjList adjList;
    int numVertexes, numEdges;
} GraphAdjList, *GraphAdjListPtr;

int TopologicalSort(GraphAdjListPtr GL) {
    EdgeNode *e;
    int i, k, gettop;
    int top = 0, count = 0;
    int *stack = (int*)malloc(GL->numVertexes * sizeof(int));

    // 入度為 0 入堆疊
    for (i = 0; i < GL->numVertexes; i++)
        if (GL->adjList[i].in == 0)
            stack[++top] = i;

    while (top != 0) {
        gettop = stack[top--];
        printf("%d -> ", GL->adjList[gettop].data);
        count++;

        for (e = GL->adjList[gettop].firstedge; e; e = e->next) {
            k = e->adjvex;
            if (--GL->adjList[k].in == 0)
                stack[++top] = k;
        }
    }

    free(stack);
    return (count < GL->numVertexes) ? -1 : 0;  // -1 表有環
}

複雜度

時間：O(n + e) — 每頂點進出堆疊一次，每邊處理一次
空間：O(n) — 入度陣列、堆疊

關鍵路徑演算法

核心概念

• ve(i)：事件 i 最早發生時間 (從源點前向傳遞)
• vl(i)：事件 i 最晚發生時間 (從匯點後向傳遞)
• 活動 k = 弧 <m, n>：
  • e(k) = ve(m)：活動最早開始時間
  • l(k) = vl(n) - dut(<m,n>)：活動最晚開始時間
• 關鍵活動：e(k) == l(k)，無浮動時間
• 關鍵路徑：由關鍵活動構成的路徑，決定專案最短工期

演算法流程

1. 拓撲排序同時計算 ve[] (最早時間)
2. 若有環 → 結束
3. 初始化 vl[] = ve[終點]
4. 逆拓撲序計算 vl[] (最晚時間)
5. 掃描所有弧，找出 e(k) == l(k) 的關鍵活動

程式碼實作

int *etv, *ltv;      // 全域：最早/最晚時間
int *stack2;         // 拓撲序列堆疊
int top2;

int TopologicalSort(GraphAdjListPtr GL) {
    // ... 前面拓撲排序程式碼 ...
    // 關鍵差異：計算 etv (最早時間)
    top2 = 0;
    etv = (int*)malloc(GL->numVertexes * sizeof(int));
    for (i = 0; i < GL->numVertexes; i++) etv[i] = 0;
    stack2 = (int*)malloc(GL->numVertexes * sizeof(int));

    while (top != 0) {
        gettop = stack[top--];
        stack2[++top2] = gettop;  // 記錄拓撲序列
        count++;

        for (e = GL->adjList[gettop].firstedge; e; e = e->next) {
            k = e->adjvex;
            if (--GL->adjList[k].in == 0)
                stack[++top] = k;
            // 更新最早時間：ve[k] = max(ve[k], ve[gettop] + weight)
            if (etv[gettop] + e->weight > etv[k])
                etv[k] = etv[gettop] + e->weight;
        }
    }
    // ...
}

void CriticalPath(GraphAdjListPtr GL) {
    EdgeNode *e;
    int i, gettop, k, ete, lte;

    TopologicalSort(GL);  // 取得 etv[] 和 stack2[]

    ltv = (int*)malloc(GL->numVertexes * sizeof(int));
    for (i = 0; i < GL->numVertexes; i++)
        ltv[i] = etv[GL->numVertexes - 1];  // 初始化為專案最早完成時間

    // 逆拓撲序計算 ltv (最晚時間)
    while (top2 != 0) {
        gettop = stack2[top2--];
        for (e = GL->adjList[gettop].firstedge; e; e = e->next) {
            k = e->adjvex;
            if (ltv[k] - e->weight < ltv[gettop])
                ltv[gettop] = ltv[k] - e->weight;
        }
    }

    // 找出關鍵活動
    for (i = 0; i < GL->numVertexes; i++) {
        for (e = GL->adjList[i].firstedge; e; e = e->next) {
            k = e->adjvex;
            ete = etv[i];           // 活動最早開始
            lte = ltv[k] - e->weight; // 活動最晚開始
            if (ete == lte)
                printf("關鍵活動 <v%d,v%d> 長度:%d\n", 
                    GL->adjList[i].data, GL->adjList[k].data, e->weight);
        }
    }

    free(etv); free(ltv); free(stack2);
}

實戰範例解析

文章圖示專案：關鍵路徑為 V0→V1→V3→V5→V7，總工期 18 天。關鍵活動無延遲空間，非關鍵活動 (如 V1→V2) 有浮動時間可調度資源。

總結比較