最小生成樹：Prim 與 Kruskal 算法詳解（以 HDU 1863 為例）

最小生成樹（MST）算法對比：Prim vs Kruskal

MST 性質

設 G=(V,E) 為連通帶權圖，U 為 V 的真子集。若邊 (u,v) 滿足 u∈U, v∈V-U，且權值最小，則存在某棵 MST 包含該邊（割性質）。

Prim 算法（適合稠密圖）

思想：維護已選頂點集合 S，初始任選一點。重複 n-1 次：選取一條連接 S 與 V-S 的最小權邊，將新頂點加入 S。用 low[v] 記錄 v 到 S 的最小邊權。

代碼要點：

int prim() {
    memset(vis, 0, sizeof(vis));
    vis[1] = 1;
    for (i=2..n) low[i] = map[1][i];
    for (i=1; i
時間複雜度 O(n²)，與邊數無關，適合稠密圖（邊數接近 n²）。

Kruskal 算法（適合稀疏圖）
思想：將所有邊按權升序排序。初始每頂點自成連通分量。遍歷邊：若邊兩端點屬於不同分量（并查集判斷），加入 MST，合併分量。直到選取 n-1 條邊。
代碼要點：
struct Edge { int u, v, w; };
sort(edges, edges+m, cmp); // 按 w 升序
for (i=1..n) fa[i] = i; // 并查集初始化
for (each edge) {
    int fu = find(u), fv = find(v);
    if (fu != fv) { ans += w; fa[fu] = fv; if (++cnt == n-1) break; }
}
時間複雜度 O(E log E)（排序主導），適合稀疏圖（E ≪ V²）。

對比總結

算法
時間複雜度
適用圖
核心數據結構
Prim
O(V²)
稠密圖
數組 low[]、訪問標記
Kruskal
O(E log E)
稀疏圖
并查集、邊排序


HDU 1863 範例
輸入：m 條道路，n 個村莊。求連通所有村莊的最小總長度。若不可連通輸出 "?"。

Prim 版與 Kruskal 版代碼均已給出，可直接參考。

進階：過程演示
文中還給出了具體圖上兩算法的選邊過程演示，有助於理解動態選擇差異。