C語言實現Prim算法求最小生成樹完整指南

編輯：關於C語言

Prim算法原理與C語言實現詳解

最小生成樹（Minimum Spanning Tree，MST）是圖論中的經典問題，Prim算法作為求解MST的貪心算法之一，以其簡潔高效的特點被廣泛應用。本文將深入解析Prim算法的核心邏輯，並提供完整的C語言實現代碼。

算法核心思想

Prim算法從任意一個頂點開始，維護一個已選頂點集合，每次從未選頂點中選擇一條連接已選集合且權重最小的邊，將新頂點加入集合，直到所有頂點都被包含。這種「最近鄰擴展」策略保證了生成樹的總權重最小。

數據結構設計

實現中採用鄰接矩陣存儲圖結構，定義邊結構體包含起點、終點和權重。關鍵數據結構如下：

#define MAX_VERTICES 6
#define INF 10000

typedef int AdjMatrix[MAX_VERTICES + 1][MAX_VERTICES + 1];

typedef struct {
    int fromvex, tovex;
    int weight;
} Edge;

關鍵步驟實現

1. 圖的創建與初始化

通過鄰接矩陣建立圖，初始化對角線為0，其餘為無窮大（INF），再根據用戶輸入的邊信息填充矩陣。

2. Prim算法主流程

算法從頂點1出發，初始化候選邊集合為從頂點1到其他所有頂點的邊。然後進行n-1輪選擇：每輪從候選邊中選取權重最小且終點未在樹中的邊，加入生成樹，並更新候選邊集合（將新加入頂點連接未選頂點的邊加入候選集，若權重更小則替換）。

void Prim(AdjMatrix GA, Edge *T) {
    int i, j, k, min, u, m, w;
    Edge temp;
    
    // 初始化候選邊：從頂點1到其他頂點
    k = 1;
    for (i = 1; i <= MAX_VERTICES; i++) {
        if (i != 1) {
            T[k].fromvex = 1;
            T[k].tovex = i;
            T[k].weight = GA[1][i];
            k++;
        }
    }
    
    // 進行n-1次選擇
    for (k = 1; k < MAX_VERTICES; k++) {
        // 在T[k..n-1]中找最小邊
        min = INF;
        m = k;
        for (i = k; i < MAX_VERTICES; i++) {
            if (T[i].weight < min) {
                min = T[i].weight;
                m = i;
            }
        }
        
        // 交換將最小邊移到位置k
        if (m != k) {
            temp = T[k];
            T[k] = T[m];
            T[m] = temp;
        }
        
        // 更新候選邊集合
        u = T[k].tovex;  // 新加入頂點
        for (i = k + 1; i < MAX_VERTICES; i++) {
            j = T[i].tovex;
            w = GA[u][j];
            if (w < T[i].weight) {
                T[i].weight = w;
                T[i].fromvex = u;
            }
        }
    }
}