C 語言克魯斯卡爾算法整合並查集完整實作

核心思想

克魯斯卡爾算法：邊按權重排序，依序加入不形成環的邊。
並查集：O(α(n)) 判斷兩頂點是否同連通分量 (即是否會成環)。

完整代碼

#include 
#include 
#include 

#define MAX_V 100
#define MAX_E 1000

typedef struct {
    int u, v, w;
} Edge;

typedef struct {
    int parent[MAX_V];
    int rank[MAX_V];
} UnionFind;

// 並查集初始化
void uf_init(UnionFind *uf, int n) {
    for (int i = 0; i < n; i++) {
        uf->parent[i] = i;
        uf->rank[i] = 0;
    }
}

// 尋找根節點 (路徑壓縮)
int uf_find(UnionFind *uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = uf_find(uf, uf->parent[x]);
    }
    return uf->parent[x];
}

// 合併兩集合 (按秩合併)
void uf_union(UnionFind *uf, int x, int y) {
    int rx = uf_find(uf, x);
    int ry = uf_find(uf, y);
    if (rx == ry) return;
    if (uf->rank[rx] < uf->rank[ry]) {
        uf->parent[rx] = ry;
    } else if (uf->rank[rx] > uf->rank[ry]) {
        uf->parent[ry] = rx;
    } else {
        uf->parent[ry] = rx;
        uf->rank[rx]++;
    }
}

// 邊比較函數 (qsort 用)
int cmp_edge(const void *a, const void *b) {
    return ((Edge*)a)->w - ((Edge*)b)->w;
}

// 克魯斯卡爾主函數
int kruskal(Edge edges[], int e, int v, Edge mst[]) {
    qsort(edges, e, sizeof(Edge), cmp_edge);
    
    UnionFind uf;
    uf_init(&uf, v);
    
    int mst_count = 0;
    int mst_weight = 0;
    
    for (int i = 0; i < e && mst_count < v - 1; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;
        
        // 並查集判斷是否成環
        if (uf_find(&uf, u) != uf_find(&uf, v)) {
            uf_union(&uf, u, v);
            mst[mst_count++] = edges[i];
            mst_weight += w;
        }
    }
    
    return (mst_count == v - 1) ? mst_weight : -1; // -1 表示圖不連通
}

// 測試主程式
int main() {
    int v = 6; // 頂點數
    int e = 9; // 邊數
    Edge edges[] = {
        {0, 1, 4}, {0, 2, 4}, {1, 2, 2},
        {1, 0, 4}, {2, 0, 4}, {2, 1, 2},
        {2, 3, 3}, {2, 5, 2}, {2, 4, 4},
        {3, 2, 3}, {3, 4, 3}, {4, 2, 4},
        {4, 3, 3}, {4, 5, 3}, {5, 2, 2},
        {5, 4, 3}
    };
    // 去重 (無向圖只需一向)
    Edge unique_edges[MAX_E];
    int ue = 0;
    for (int i = 0; i < e; i++) {
        if (edges[i].u < edges[i].v) { // 只保留 u < v
            unique_edges[ue++] = edges[i];
        }
    }
    
    Edge mst[MAX_V];
    int weight = kruskal(unique_edges, ue, v, mst);
    
    if (weight == -1) {
        printf("圖不連通，無最小生成樹\n");
    } else {
        printf("最小生成樹權重: %d\n", weight);
        printf("邊列表:\n");
        for (int i = 0; i < v - 1; i++) {
            printf("  %d - %d (權重: %d)\n", mst[i].u, mst[i].v, mst[i].w);
        }
    }
    return 0;
}

關鍵點解析

優化技巧

1. 路徑壓縮：`find` 時將沿途節點直接指向根
2. 按秩合併：樹高較小的合併到較大，控制樹高
3. 邊去重：無向圖只存 u < v 的邊
4. 早停：MST 邊數達 V-1 即停止

C++ 版本 (STL 更簡潔)

struct DSU {
    vector p, r;
    DSU(int n): p(n), r(n,0) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x]==x?x:p[x]=find(p[x]); }
    bool unite(int a, int b) {
        a=find(a); b=find(b); if(a==b) return false;
        if(r[a]& edges, int n, vector& mst) {
    sort(edges.begin(), edges.end(), [](auto&a,auto&b){return a.w