您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

克魯斯卡爾演算法 C 語言實現詳解（中）：排序、查找與合併三大核心模組

編輯：關於C

承接上篇圖結構定義，本文深入剖析克魯斯卡爾演算法三大核心難點：邊權排序、環路檢測（查找）、樹合併，提供通用排序框架與具體實現代碼。

一、通用冒泡排序框架（函數指針多態）

為對結構體陣列排序，設計接受比較與交換回調的通用排序器：

void bubble_sort(void* arr[], int n, 
                 int (*cmp)(void*, void*), 
                 void (*swp)(void**, void**)) {
    for (int i = n-1; i > 0; --i)
        for (int j = 0; j < i; ++j)
            if (cmp(arr[j], arr[j+1]))
                swp(&arr[j], &arr[j+1]);
}

二、針對 DIR_LINE 結構的回調實現

typedef struct { int u, v, weight; } DIR_LINE;

int cmpEdge(void* a, void* b) {
    DIR_LINE* p1 = (DIR_LINE*)a;
    DIR_LINE* p2 = (DIR_LINE*)b;
    return p1->weight > p2->weight;  // 升序
}

void swpEdge(void** a, void** b) {
    DIR_LINE* tmp = *(DIR_LINE**)a;
    *(DIR_LINE**)a = *(DIR_LINE**)b;
    *(DIR_LINE**)b = tmp;
}

三、環路檢測：判斷兩頂點是否已在同一最小生成樹

// 統計樹中包含頂點 v 的數量（0/1/2）
int countVertexInTree(MINI_GENERATE_TREE* t, int v) {
    int cnt = 0;
    for (int i = 0; i < t->node_num; ++i)
        if (t->pNode[i] == v) ++cnt;
    return cnt;
}

// 檢查 u,v 是否同時存在於某棵樹中
int isBothInSameTree(MINI_GENERATE_TREE** trees, int treeCnt, int u, int v) {
    for (int i = 0; i < treeCnt; ++i) {
        int c = 0;
        c += countVertexInTree(trees[i], u);
        c += countVertexInTree(trees[i], v);
        if (c == 2) return 1;  // 同樹 → 會成環
    }
    return 0;
}

四、樹合併：將兩棵樹合為一棵

void mergeTrees(MINI_GENERATE_TREE** trees, int* treeCnt, 
                int u, int v, int w) {
    // 找到包含 u、v 的兩棵樹
    MINI_GENERATE_TREE *t1 = NULL, *t2 = NULL;
    int idx1 = -1, idx2 = -1;
    for (int i = 0; i < *treeCnt; ++i) {
        if (countVertexInTree(trees[i], u)) { t1 = trees[i]; idx1 = i; }
        if (countVertexInTree(trees[i], v)) { t2 = trees[i]; idx2 = i; }
    }
    if (!t1 || !t2 || t1 == t2) return;  // 同樹或不存在
    
    // 合併節點陣列
    for (int i = 0; i < t2->node_num; ++i)
        t1->pNode[t1->node_num++] = t2->pNode[i];
    
    // 合併邊鏈表
    for (DIR_LINE* e = t2->pLine; e; e = e->next)
        insertLine(&t1->pLine, e->u, e->v, e->weight);
    insertLine(&t1->pLine, u, v, w);  // 加入當前邊
    
    // 移除 t2
    for (int i = idx2; i < *treeCnt - 1; ++i)
        trees[i] = trees[i+1];
    --(*treeCnt);
}