圖論核心演算法實現：拓撲排序、關鍵路徑、最短路徑（Dijkstra）

圖的鄰接矩陣存儲結構

template 
class GraphMtx : public Graph {
    V* vertices;      // 頂點表
    E** edges;        // 鄰接矩陣
    int maxVertices, numVertices, numEdges;
    // ... 基本操作：插入頂點/邊、獲取鄰接頂點、獲取頂點索引等
};

一、拓撲排序

定義：對有向無環圖（DAG）頂點排序，使所有邊 (u,v) 滿足 u 在 v 之前。
算法：Kahn 算法（BFS 基於入度）。

1. 統計所有頂點入度。
2. 入度為 0 的頂點入棧/隊列。
3. 彈出頂點輸出，刪除其出邊，更新鄰接頂點入度，入度變 0 者入棧。
4. 重複至棧空。若輸出頂點數 < 總頂點數，圖有環。

void topological_sort() {
    int n = numVertices;
    int* inDegree = new int[n]();
    // 計算入度
    for (int i = 0; i < n; ++i)
        for (int j = getFirstNeighbor(i); j != -1; j = getNextNeighbor(i, j))
            ++inDegree[j];

    int* stack = new int[n];
    int top = -1;
    // 入度為 0 入棧
    for (int i = 0; i < n; ++i) if (inDegree[i] == 0) stack[++top] = i;

    while (top != -1) {
        int v = stack[top--];
        cout << vertices[v] << " ";
        for (int j = getFirstNeighbor(v); j != -1; j = getNextNeighbor(v, j)) {
            if (--inDegree[j] == 0) stack[++top] = j;
        }
    }
    delete[] inDegree; delete[] stack;
}

二、關鍵路徑（AOV 網中的最長路徑）

概念：從源點到匯點路徑長度最長的路徑。決定項目最短工期。
核心數組：

• earlyStart[v]：頂點 v 最早開始時間 = 從源點到 v 的最長路徑長度。
• lateStart[v]：頂點 v 最晚開始時間 = 從匯點逆向計算的最長路徑長度。

關鍵頂點：earlyStart[v] == lateStart[v] 的頂點構成關鍵路徑。

void critical_path(V start) {
    int n = numVertices;
    int* early = new int[n]();
    int* late = new int[n]();
    int s = getVertexIndex(start);

    // 正向計算 early（拓撲序）
    for (int i = 0; i < n; ++i) {
        for (int j = getFirstNeighbor(i); j != -1; j = getNextNeighbor(i, j)) {
            int w = edges[i][j];
            if (early[i] + w > early[j]) early[j] = early[i] + w;
        }
    }
    // 反向計算 late（逆拓撲序），late 初始化為 early[匯點]
    fill(late, late + n, early[n-1]); // 假設最後一個為匯點
    for (int i = n - 2; i >= 0; --i) {
        for (int j = getFirstNeighbor(i); j != -1; j = getNextNeighbor(i, j)) {
            int w = edges[i][j];
            if (late[j] - w < late[i]) late[i] = late[j] - w;
        }
    }
    // 輸出關鍵路徑頂點
    for (int i = 0; i < n; ++i)
        if (early[i] == late[i]) cout << vertices[i] << " ";
    delete[] early; delete[] late;
}

三、最短路徑——Dijkstra 算法

適用：無負權邊的單源最短路徑。
核心數組：

• dist[v]：源點到 v 當前最短距離。
• path[v]：最短路徑上 v 的前驅頂點。
• collected[v]：是否已確定最短路徑（納入集合）。

void shortest_path(V start) {
    int n = numVertices;
    int* dist = new int[n];
    int* path = new int[n];
    bool* collected = new bool[n]();

    fill(dist, dist + n, MAX_COST);
    fill(path, path + n, -1);
    int s = getVertexIndex(start);
    dist[s] = 0;

    for (int i = 0; i < n; ++i) {
        // 選擇未收錄且 dist 最小的頂點
        int v = -1, minDist = MAX_COST;
        for (int j = 0; j < n; ++j)
            if (!collected[j] && dist[j] < minDist) { minDist = dist[j]; v = j; }
        if (v == -1) break; // 剩餘不可達
        collected[v] = true;

        // 松弛操作
        for (int j = getFirstNeighbor(v); j != -1; j = getNextNeighbor(v, j)) {
            if (!collected[j] && edges[v][j] < MAX_COST) {
                if (dist[v] + edges[v][j] < dist[j]) {
                    dist[j] = dist[v] + edges[v][j];
                    path[j] = v;
                }
            }
        }
    }
    // 輸出路徑與距離...
    delete[] dist; delete[] path; delete[] collected;
}

完整代碼結構

包含 Graph.h（抽象基類）、GraphMtx.h（鄰接矩陣實現）、測試主程式。測試涵蓋三種演算法在同一圖上的驗證。