Prim 算法求最小生成樹：C++ 鄰接矩陣完整實現與圖解

算法原理

Prim 算法以貪心策略構建最小生成樹 (MST)：

1. 維護兩個集合：U（已在 MST 中的頂點）、T（MST 的邊）；
2. 初始 U={任意起點}，T=∅；
3. 重復：從連接 U 與 V-U 的邊中選權值最小者 (u,v)，將 v 加入 U，邊加入 T；
4. 直到 U=V。

圖解演示 (以 G4 為例，起點 A)

1. U={A} → 選邊 (A,B,權5) → U={A,B}
2. 選 (B,F,權6) → U={A,B,F}
3. 選 (F,E,權7) → U={A,B,F,E}
4. 選 (E,D,權8) → U={A,B,F,E,D}
5. 選 (D,C,權5) → U={A,B,F,E,D,C}
6. 選 (F,G,權9) → U=V，完成。MST 權和 = 5+6+7+8+5+9 = 40。

C++ 鄰接矩陣實現

數據結構

class MatrixUDG {
    #define MAX 100
    #define INF 0x7FFFFFFF
    char mVexs[MAX];        // 頂點名
    int mVexNum, mEdgNum;   // 頂點數、邊數
    int mMatrix[MAX][MAX];  // 鄰接矩陣，INF 表示無邊
    // ... 輔助函數 ...
public:
    void prim(int start);   // 從 start 索引開始
};

核心 prim 函數

void MatrixUDG::prim(int start) {
    int min, i, j, k, sum = 0;
    char prims[MAX];        // MST 頂點序列
    int weights[MAX];       // 非樹頂點到樹的最小邊權

    prims[0] = mVexs[start];
    for (i = 0; i < mVexNum; ++i) weights[i] = mMatrix[start][i];
    weights[start] = 0;     // 起點權設 0，標記已入樹

    for (i = 1; i < mVexNum; ++i) {  // 需加入 V-1 個頂點
        min = INF; k = -1;
        for (j = 0; j < mVexNum; ++j)
            if (weights[j] != 0 && weights[j] < min)  // 未入樹且權最小
                min = weights[j], k = j;

        prims[i] = mVexs[k];
        weights[k] = 0;     // 標記入樹

        // 更新非樹頂點到樹的最小邊權
        for (j = 0; j < mVexNum; ++j)
            if (weights[j] != 0 && mMatrix[k][j] < weights[j])
                weights[j] = mMatrix[k][j];
    }

    // 計算總權（驗證用）
    for (i = 1; i < mVexNum; ++i) {
        min = INF;
        int n = getPosition(prims[i]);
        for (j = 0; j < i; ++j) {
            int m = getPosition(prims[j]);
            if (mMatrix[m][n] < min) min = mMatrix[m][n];
        }
        sum += min;
    }
    // 輸出結果...
}

關鍵細節

複雜度

• 鄰接矩陣 + 數組掃描：O(V²)，適合稠密圖；
• 鄰接表 + 優先隊列：O(E log V)，適合稀疏圖。

結語

Prim 算法是 MST 的經典貪心算法。鄰接矩陣版本代碼簡潔、適合教學與中小規模稠密圖。掌握其「邊權維護 + 貪心選擇」核心邏輯，易於擴展到鄰接表優化版本。