圖論經典：Prim 算法求最小生成樹（C 語言完整實現）

Prim 算法深度解析與 C 語言實現

最小生成樹（Minimum Spanning Tree, MST）是圖論核心問題，廣泛應用於網絡設計、電路佈線、聚類分析等領域。Prim 算法作為構造 MST 的經典貪心算法，以 O(n²) 時間複雜度成為稠密圖的首選。本文從原理、步驟、代碼實現到運行演示全方位講解。

算法原理

給定連通網 G=(V,E)，權值為邊的代價。Prim 算法思想：

1. 任選一頂點 v₁ 入集合 U，邊集 TE 為空。
2. 重複：在連接 U 和 V-U 的邊中選權值最小者 (vᵢ, vⱼ)，將 vⱼ 並入 U，邊並入 TE。
3. 直到 U = V，TE 含 n-1 條邊，即得 MST。

關鍵數據結構：edge[] 數組動態維護從 U 到 V-U 的最小代價邊，每次選擇後更新。

算法步驟

1. 初始化 edge[]，記錄起始頂點到其餘頂點的最小邊。
2. 將起始頂點標記為已入樹（cost=0）。
3. 循環 n-1 次：
   　a. 從 edge[] 中找 cost>0 且最小的邊；
   　b. 將該邊終點加入樹，輸出邊信息；
   　c. 以新頂點為基準，更新 edge[] 中未入樹頂點的最小邊。

核心代碼實現

typedef struct { int start, end, cost; } Edge;

void Prim_MG(MGraph MG, char vs) {
    Edge edge[MAX_VEX_NUM];
    int i, j, k, v, min;
    int s = getIndexOfVexs(vs, &MG);

    // 1. 初始化邊數組
    for (i = 1; i <= MG.vexnum; i++) {
        if (s != i) {
            edge[i].start = s;
            edge[i].end = i;
            edge[i].cost = MG.arcs[s][i];
        }
    }
    edge[s].cost = 0; // 起點入樹

    // 2. 選擇 n-1 條邊
    for (i = 2; i <= MG.vexnum; i++) {
        min = UN_REACH;
        for (j = 1; j <= MG.vexnum; j++)
            if (edge[j].cost != 0 && edge[j].cost < min) {
                min = edge[j].cost; k = j;
            }
        v = edge[k].end;
        edge[v].cost = 0; // 新頂點入樹
        printf("%c %c %d\n", MG.vexs[edge[v].start], MG.vexs[edge[v].end], MG.arcs[edge[v].start][edge[v].end]);

        // 3. 更新邊數組
        for (j = 1; j <= MG.vexnum; j++)
            if (edge[j].cost != 0 && MG.arcs[v][j] != 0 && MG.arcs[v][j] < edge[j].cost) {
                edge[j].start = k;
                edge[j].end = j;
                edge[j].cost = MG.arcs[v][j];
            }
    }
}

完整可運行程序

包含圖的創建（鄰接矩陣）、打印、Prim 算法調用及主函數，支持有向/無向圖輸入。

/* 完整代碼見原文，關鍵結構定義： */
#define MAX_VEX_NUM 50
#define UN_REACH 1000
typedef char VertexType;
typedef enum { DG, UDG } GraphType;
typedef struct {
    VertexType vexs[MAX_VEX_NUM];
    int arcs[MAX_VEX_NUM][MAX_VEX_NUM];
    int vexnum, arcnum;
    GraphType type;
} MGraph;
/* ... create_MG, print_MG, getIndexOfVexs, main 等輔助函數 ... */

運行演示

輸入：
無向圖，4頂點(a,b,c,d)，5條邊
a-b:1  a-c:3  a-d:4  b-c:2  c-d:3
起始頂點：a

輸出：
a b 1
b c 2
c d 3
// 總權值 6，構成最小生成樹

複雜度分析與適用性

• 時間複雜度： O(n²)，與邊數無關，適合稠密圖（邊數接近 n²）。
• 空間複雜度： O(n) 輔助數組。
• 稀疏圖（邊數少）建議使用 Kruskal 算法 O(e log e) 或優先隊列優化的 Prim O(e log n)。

常見問題與優化

• 圖不連通： 算法會提前終止，需預檢連通性。
• 權值相同邊： 任選其一，不影響總權值最小性。
• 優化方向： 使用最小堆維護候選邊，將查找最小邊從 O(n) 降為 O(log n)，總複雜度達 O(e log n)。