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

克魯斯卡爾演算法詳解：尋找最小生成樹的經典方法

編輯：關於C

前言

克魯斯卡爾演算法是解決最小生成樹問題的兩大經典演算法之一（另一個是 Prim 演算法）。不同於 Prim 演算法以節點為中心擴展，克魯斯卡爾演算法採用「邊優先」的貪婪策略：將所有邊按權重排序，再依序檢查是否形成環路，從而構建最小生成樹。本文將透過圖解與程式碼，帶您逐步理解其核心邏輯與 C 語言實作細節。

演算法核心邏輯

假設圖有 m 個節點、n 條邊。演算法流程如下：

將每個節點視為獨立的生成樹（共 m 棵樹）。
將所有邊依權重由小到大排序。
依序取出邊：若該邊的兩端點屬於不同的樹，則合併兩樹；若屬同一樹（會形成環），則捨棄該邊。
重複直到遍歷所有邊。若最終合併為單一樹，即為最小生成樹；否則圖不連通，無最小生成樹。

關鍵在於如何高效判斷「兩端點是否屬於同一樹」——這通常由「並查集」資料結構實現，本文採用陣列模擬的簡易版本。

圖解範例演示

考慮一個包含 4 個節點（A、B、C、D）與 5 條邊的無向圖：

   3       6
A ------- B
| \       |
|  \ 7    | 5
|   \     |
|    \    |
D ------- C
    9

邊權重列表：A-D(3)、B-C(5)、A-B(6)、A-C(7)、B-D(9)。

步驟 1：初始狀態

四個節點各自獨立：

A   B   C   D

步驟 2：加入最小邊 A-D (3)

A 與 D 合併：

A---D   B   C

步驟 3：加入次小邊 B-C (5)

B 與 C 合併：

A---D   B---C

步驟 4：加入邊 A-B (6)

發現 A 屬於 {A,D}，B 屬於 {B,C}，不同樹 → 合併：

A---D
|    |
B---C

此時已連通所有節點，剩餘邊 A-C(7)、B-D(9) 會形成環，故捨棄。最終最小生成樹權重總和 = 3+5+6 = 14。

資料結構定義

為了實作演算法，需定義圖、邊、最小生成樹等結構：

/* 直連邊：記錄起點、終點、權重 */
typedef struct _DIR_LINE {
    int start;
    int end;
    int weight;
    struct _DIR_LINE* next;
} DIR_LINE;

/* 最小生成樹結構 */
typedef struct _MINI_GENERATE_TREE {
    int node_num;        // 節點數
    int line_num;        // 邊數
    int* pNode;          // 節點陣列
    DIR_LINE* pLine;     // 邊鏈表
} MINI_GENERATE_TREE;

/* 圖的鄰接表節點 */
typedef struct _LINE {
    int end;
    int weight;
    struct _LINE* next;
} LINE;

typedef struct _VECTEX {
    int start;
    int number;
    LINE* neighbor;
    struct _VECTEX* next;
} VECTEX;

typedef struct _GRAPH {
    int count;
    VECTEX* head;
} GRAPH;

關鍵函數實作

演算法主流程 get_mini_tree_from_graph 採用自頂向下設計，依賴三個核心子函數：

get_dir_line_from_graph：從圖中收集所有候選邊，過濾無效邊（兩端點已在樹中），排序後取最小者。
delete_unvalid_line_from_list：移除雙端點皆已在生成樹中的邊。
check_valid_for_line：檢查邊是否有效（至少一端點不在樹中）。
insert_node_into_mini_tree：將新節點加入生成樹節點陣列。
sort_for_line_list：對邊鏈表按權重進行插入排序。

邊有效性檢查

int check_valid_for_line(DIR_LINE* pDirLine, MINI_GENERATE_TREE* pMiniTree) {
    int flag_start = 0, flag_end = 0;
    for (int i = 0; i < pMiniTree->node_num; i++) {
        if (pDirLine->start == pMiniTree->pNode[i]) flag_start = 1;
        if (pDirLine->end == pMiniTree->pNode[i]) flag_end = 1;
    }
    // 若兩端點都在樹中 → 無效 (回傳 0)
    return (flag_start && flag_end) ? 0 : 1;
}

鏈表插入排序

void insert_for_sort_operation(DIR_LINE** ppNode, DIR_LINE* pNode) {
    if (pNode->weight < (*ppNode)->weight) {
        pNode->next = *ppNode;
        *ppNode = pNode;
        return;
    }
    DIR_LINE* cur = *ppNode;
    DIR_LINE* prev = NULL;
    while (cur) {
        if (pNode->weight < cur->weight) break;
        prev = cur;
        cur = cur->next;
    }
    pNode->next = prev->next;
    prev->next = pNode;
}

void sort_for_line_list(DIR_LINE** ppNode) {
    if (!ppNode || !*ppNode) return;
    DIR_LINE* curr = (*ppNode)->next;
    (*ppNode)->next = NULL;
    while (curr) {
        DIR_LINE* prev = curr;
        curr = curr->next;
        insert_for_sort_operation(ppNode, prev);
    }
}