手把手寫演算法：Kruskal 最小生成樹完整實現（中）

承接上篇，Kruskal 演算法三大核心挑戰：邊排序、樹查找、樹合併。本文逐一攻克，採用通用排序框架、陣列式樹管理與節點計數查找策略。

1. 通用氣泡排序框架

為排序 DIR_LINE* 陣列，設計函數指標版氣泡排序：

void bubble_sort(void* array[], int length,
                 int (*compare)(void*, void*),
                 void (*swap)(void**, void**)) {
    for (int outer = length - 1; outer > 0; outer--)
        for (int inner = 0; inner < outer; inner++)
            if (compare(array[inner], array[inner + 1]))
                swap(&array[inner], &array[inner + 1]);
}

DIR_LINE 專用比較與交換

int compare(void* data1, void* data2) {
    DIR_LINE* line1 = (DIR_LINE*)data1;
    DIR_LINE* line2 = (DIR_LINE*)data2;
    return (line1->weight > line2->weight) ? 1 : 0;  // 升序
}

void swap(void** data1, void** data2) {
    DIR_LINE* median = *(DIR_LINE**)data1;
    *(DIR_LINE**)data1 = *(DIR_LINE**)data2;
    *(DIR_LINE**)data2 = median;
}

優點：排序邏輯與資料型別解耦，可復用於任意結構體陣列排序。

2. 節點計數查找策略

判斷邊 (start, end) 是否跨樹：統計兩端點在各樹中的出現次數。

// 統計單棵樹中 start/end 出現總次數 (0, 1, 或 2)
int getVectexNumFromTree(MINI_GENERATE_TREE* pTree, int start, int end) {
    int total = 0;
    for (int i = 0; i < pTree->node_num; i++) {
        if (start == pTree->pNode[i]) { total++; continue; }
        if (end == pTree->pNode[i]) total++;
    }
    return total;
}

// 檢查是否有樹同時包含 start 和 end (total == 2)
int isDoubleVectexExistInTree(MINI_GENERATE_TREE* pTree[], int length, int start, int end) {
    int maxVal = 0;
    for (int i = 0; i < length; i++) {
        int num = getVectexNumFromTree(pTree[i], start, end);
        if (num > maxVal) maxVal = num;
    }
    return (maxVal == 2) ? 1 : 0;  // 存在樹同時含兩端點 → 同樹
}

邏輯：若某樹計數為 2，說明兩端點在同樹 → 捨棄該邊；否則跨樹 → 合併。

3. 樹合併操作

將兩棵樹合併為一棵：刪除其中一棵，節點與邊全數遷移至另一棵，並加入當前邊。

void mergeTwoMiniGenerateTree(MINI_GENERATE_TREE* pTree[], int length,
                              int start, int end, int weight) {
    MINI_GENERATE_TREE *pFirst = find_tree_by_index(start);
    MINI_GENERATE_TREE *pSec   = find_tree_by_index(end);

    delete_mini_tree_from_group(pTree, length, pSec);  // 從群組移除 pSec

    // 合併節點
    for (int i = 0; i < pSec->node_num; i++)
        pFirst->pNode[pFirst->node_num + i] = pSec->pNode[i];
    pFirst->node_num += pSec->node_num;

    // 合併邊
    for (DIR_LINE* line = pSec->pLine; line; line = line->next)
        insert_line_into_queue(&pFirst->pLine, line->start, line->end, line->weight);

    // 加入當前邊
    insert_line_into_queue(&pFirst->pLine, start, end, weight);
}

假設函數：find_tree_by_index 根據節點找到所屬樹；delete_mini_tree_from_group 從樹陣列移除指定樹；insert_line_into_queue 尾插入邊鏈表。下篇將完善這些輔助函數並串聯完整流程。

本篇小結

將複雜問題分解為排序、查找、合併三個獨立子問題，各個擊破，是演算法工程化的核心思想。下篇將完成剩餘輔助函數並展示完整主流程。