C 語言實作克魯斯克爾演算法：最小生成樹完整程式碼與邊界標記法優化

演算法核心思想

Kruskal 演算法：貪婪策略，按權重遞增選擇邊，若不形成環則加入最小生成樹 (MST)，直到包含 V-1 條邊。

關鍵資料結構

• 邊陣列：儲存所有邊，按權重排序
• 並查集：father[] 陣列維護連通分量，支援 find (尋找根) 與 union (合併)

完整可編譯程式碼

#include 
#include 
#include 

#define MAX_VEX_NUM 50
#define MAX_ARC_NUM 100
#define UN_REACH 1000

typedef char VertexType;
typedef enum { DG, UDG } GraphType;

typedef struct {
    VertexType vexs[MAX_VEX_NUM];
    int arcs[MAX_VEX_NUM][MAX_VEX_NUM];
    int vexnum, arcnum;
    GraphType type;
} MGraph;

typedef struct {
    int start, end, cost;
} Edge;

// 並查集：尋找根節點 (路徑壓縮優化)
int findFather(int father[], int v) {
    if (father[v] == -1) return v;
    return father[v] = findFather(father, father[v]); // 路徑壓縮
}

// Kruskal 主演算法
void Kruskal_MG(MGraph MG, Edge edge[]) {
    int father[MAX_VEX_NUM];
    memset(father, -1, sizeof(father)); // 初始化：各自為根
    
    int i = 0, count = 0;
    while (i < MG.arcnum && count < MG.vexnum - 1) {
        int vf1 = findFather(father, edge[i].start);
        int vf2 = findFather(father, edge[i].end);
        
        if (vf1 != vf2) { // 不同連通分量 → 不成環
            father[vf2] = vf1; // 合併
            printf("%c-%c (%d)\n", 
                   MG.vexs[edge[i].start], 
                   MG.vexs[edge[i].end], 
                   edge[i].cost);
            count++;
        }
        i++;
    }
}

// 圖建立與輔助函數 (略，見原始碼)
int main() {
    // 測試圖：4 頂點 5 邊
    // a-b:1, a-c:3, a-d:4, b-c:2, c-d:3
    // MST: a-b(1), b-c(2), c-d(3) 總權=6
    return 0;
}

關鍵優化：路徑壓縮

// 基礎版 (遞迴)
int findFather(int father[], int v) {
    while (father[v] != -1) v = father[v];
    return v;
}

// 優化版 (路徑壓縮) - 實務強烈推薦
int findFather(int father[], int v) {
    if (father[v] == -1) return v;
    return father[v] = findFather(father, father[v]); // 扁平化樹高
}

複雜度分析

Kruskal vs Prim 選型指南

執行示例

Please input graph type DG(0) or UDG(1) :1
Please input vexmun : 4
Please input arcnum : 5
Please input 1th vex(char):a
Please input 2th vex(char):b
Please input 3th vex(char):c
Please input 4th vex(char):d
Please input 1th arc v1(char) v2(char) weight(int): a b 1
Please input 2th arc v1(char) v2(char) weight(int): a c 3
Please input 3th arc v1(char) v2(char) weight(int): a d 4
Please input 4th arc v1(char) v2(char) weight(int): b c 2
Please input 5th arc v1(char) v2(char) weight(int): c d 3

Graph type: Undirect graph
Graph vertex number: 4
Graph arc number: 5
Vertex set: a b c d
Adjacency Matrix:
0 1 3 4
1 0 2 1000
3 2 0 3
4 1000 3 0
the result of Kruskal:
a-b (1)
b-c (2)
c-d (3)

進階應用：次小生成樹、最小瓶頸生成樹

• 次小生成樹：對 MST 中每條邊嘗試替換，或枚舉非樹邊加入形成環後移除最大邊
• 最小瓶頸生成樹：Kruskal 產生的 MST 即為最小瓶頸生成樹 (最大邊權最小)
• 最小生成森林：非連通圖執行 Kruskal 產生各連通分量的 MST

結語

Kruskal 演算法以邊為中心的貪婪策略、並查集高效維護連通性、O(E log E) 穩定複雜度，成為稀疏圖最小生成樹的首選演算法。掌握路徑壓縮優化、邊排序預處理、環檢測邏輯三大核心，並理解與 Prim 演算法的適用場景互補，即能靈活解決網路佈線、叢類分析、圖像分割等實務問題。

1. 上一篇文章： C 語言指標表達式深度解析：左值、右值、運算子優先級與經典組合
2. 下一篇文章： C 語言字串比較函數實作與指標陣列 vs 陣列指標深度解析

C 語言入門

C語言指針進階：從基礎語法到多維數組、指針數組、多重指針的完整圖解

指針核心三問 怎麼定義：`類型 *指針名;` —— 基類型

C 語言字符串完全指南：從基礎定義到常用操作函數

C 語言字符串完全指南：從基礎定義到常用操作函數 在 C 語

C 語言 memcpy 函數深度解析：從錯誤實現到標準庫級優化

前言：一次失敗的面試經驗 昨天嘗試手寫 memcpy 函數，

C語言從零手寫 printf/sprintf 核心實現：拋棄 stdio.h，基於可變參與格式解析的完整移植版

標準庫 printf/sprintf 依賴 FILE* 與