C語言貪心算法實現：Prim 算法求最小生成樹（鄰接矩陣版）

算法核心思想

Prim 算法從任一頂點開始，維護一個「已在樹中」頂點集合，每次選擇連接樹內外、權重最小的邊，將新頂點加入樹中。本實現採用鄰接矩陣 + 輔助陣列 lowcost/mst，時間複雜度 O(V²)，適合稠密圖。

資料結構

#define MAX 100
#define MAXCOST 100000  // 無窮大代理

int graph[MAX][MAX];    // 鄰接矩陣，graph[i][j] = 權重，無邊=MAXCOST
int lowcost[MAX];       // lowcost[j] = 從樹內到頂點 j 的最小邊權
int mst[MAX];           // mst[j] = 對應最小邊的樹內端點

Prim 核心函數

int Prim(int graph[MAX][MAX], int n) {
    // 初始化：預設頂點 0 入樹
    for (int i=1; i<n; i++) {
        lowcost[i] = graph[0][i];
        mst[i] = 0;
    }
    lowcost[0] = 0;  // 標記 0 已在樹中

    int sum = 0;
    for (int i=1; i<n; i++) {        // 需加入 n-1 條邊
        int min = MAXCOST, minid = 0;
        // 找不在樹中、lowcost 最小的頂點
        for (int j=1; j<n; j++)
            if (lowcost[j] < min && lowcost[j] != 0) {
                min = lowcost[j];
                minid = j;
            }

        printf("邊: %d - %d  權重: %d\\n", mst[minid]+1, minid+1, min);
        sum += min;
        lowcost[minid] = 0;           // 加入樹中

        // 更新 lowcost/mst
        for (int j=1; j<n; j++)
            if (graph[minid][j] < lowcost[j]) {
                lowcost[j] = graph[minid][j];
                mst[j] = minid;
            }
    }
    return sum;
}

主程式：讀取圖並呼叫

int main() {
    int m;
    printf("頂點數: ");
    scanf("%d", &m);

    // 初始化矩陣
    for (int i=0; i<m; i++)
        for (int j=0; j<m; j++)
            graph[i][j] = (i==j) ? MAXCOST : MAXCOST;

    // 讀取上三角（無向圖）
    for (int i=0; i<m; i++)
        for (int j=i+1; j<m; j++) {
            int w;
            printf("邊 %d-%d 權重 (無邊輸入 %d): ", i+1, j+1, MAXCOST);
            scanf("%d", &w);
            graph[i][j] = graph[j][i] = w;
        }

    int cost = Prim(graph, m);
    printf("MST 總權重: %d\\n", cost);
    return 0;
}

關鍵細節

• lowcost[j] == 0 代表頂點 j 已在樹中（哨兵值）。
• 初始化時將對角線設為 MAXCOST，避免自我迴路被誤選。
• 輸出時 +1 轉為 1-based 顯示，內部 0-based 運算。
• 若圖不連通，某輪找不到 minid（min 維持 MAXCOST），需額外判斷處理。

複雜度對比

Prim vs Kruskal 選擇指南

• 稠密圖、需輸出生成樹邊序列 → Prim (矩陣版簡單高效)。
• 稀疏圖、邊已給定串列、需並查集練習 → Kruskal。
• 兩者皆為貪心算法，正確性證明依賴「割性質」。

這個 O(V²) 版本程式碼短、無動態記憶體分配，是教學與中小規模稠密圖的首選實現。