拓撲排序 C++ 詳解：算法原理、圖解與鄰接表實現

什麼是拓撲排序

對有向無環圖（DAG）的頂點排序，使得若存在路徑 `u → v`，則 `u` 在 `v` 之前。應用：任務調度、編譯依賴、課程先修關係。

Kahn 算法（BFS 版）步驟

1. 計算所有頂點的入度。
2. 將入度為 0 的頂點入隊列 Q。
3. 當 Q 非空：出隊頂點 `u` 輸出到結果；遍歷 `u` 的出邊 `u→v`，`v` 入度 -1，若變 0 入隊。
4. 若結果頂點數 < 總頂點數，圖有環，拓撲排序失敗。

圖解演示

以頂點 A-G、邊 ` ` 為例：

• 初始入度 0：B, C → 先輸出 B, C。
• 移除 B,C 邊後，A,D,F,G 入度變 0 → 輸出 A,D,F,G（按存儲順序）。
• 最後輸出 E。最終序列：B C A D F G E（或其他合法順序）。

C++ 鄰接表實現

#define MAX 100
class ListDG {
    struct ENode { int ivex; ENode* nextEdge; };
    struct VNode { char data; ENode* firstEdge; };
    int mVexNum, mEdgNum;
    VNode mVexs[MAX];
public:
    ListDG(char vexs[], int vlen, char edges[][2], int elen); // 從數據構建
    int topologicalSort(); // 返回 0 成功，1 有環，-1 內存錯誤
};

int ListDG::topologicalSort() {
    int *ins = new int[mVexNum](); // 入度
    int *queue = new int[mVexNum];
    char *tops = new char[mVexNum];
    int head = 0, rear = 0, index = 0;
    // 統計入度
    for (int i = 0; i < mVexNum; i++)
        for (ENode* p = mVexs[i].firstEdge; p; p = p->nextEdge)
            ins[p->ivex]++;
    // 入度 0 入隊
    for (int i = 0; i < mVexNum; i++)
        if (ins[i] == 0) queue[rear++] = i;
    // BFS
    while (head != rear) {
        int j = queue[head++];
        tops[index++] = mVexs[j].data;
        for (ENode* p = mVexs[j].firstEdge; p; p = p->nextEdge) {
            if (--ins[p->ivex] == 0) queue[rear++] = p->ivex;
        }
    }
    if (index != mVexNum) { /* 有環 */ return 1; }
    // 輸出 tops...
    delete[] ins; delete[] queue; delete[] tops;
    return 0;
}

關鍵點

• 入度數組初始化為 0（`new int[n]()`）。
• 隊列用數組模擬，頭尾指針 `head`, `rear`。
• 檢測環：輸出頂點數 < 總數。
• 時間 O(V+E)，空間 O(V+E)。