設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置： 程式碼之家 >> 編程語言 >  >> C語言 >> 關於C語言

數據結構C語言實現：Kruskal算法求最小生成樹完整代碼與圖解

     編輯：關於C語言

Kruskal算法：最小生成樹的經典貪心實現

Kruskal算法以邊為中心，按權值遞增選擇邊，若不形成環則加入生成樹。適用於**稀疏圖**(邊數接近頂點數)，時間複雜度O(E log E)主要來自排序。本文提供完整C實現，含圖構建、邊排序、并查集檢測環、完整測試用例。

算法核心邏輯

  1. 將圖中所有邊提取到數組edges[]
  2. 按權值升序排序邊數組
  3. 初始化并查集：每個頂點自成一個集合
  4. 遍歷排序後的邊：
    　　若邊兩端點屬於不同集合 → 加入MST，合併集合
    　　否則 → 捨棄(會形成環)
  5. 當MST邊數達到V-1時結束

完整可編譯代碼

#include <stdio.h>
#include <stdlib.h>

#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];      // 頂點表(1-based索引)
    int arcs[MAX_VEX_NUM][MAX_VEX_NUM]; // 鄰接矩陣
    int vexnum, arcnum;                // 頂點數、邊數
    GraphType type;                    // 圖類型
} MGraph;

/* 邊結構 */
typedef struct {
    int start, end;  // 起點/終點索引(1-based)
    int cost;        // 權值
} Edge;

/* ===== 輔助函數 ===== */

/* 獲取頂點在vexs中的索引(1-based) */
int getIndexOfVexs(char vex, MGraph *MG) {
    for (int i = 1; i <= MG->vexnum; i++)
        if (MG->vexs[i] == vex) return i;
    return 0;  // 未找到
}

/* 創建圖：交互式輸入 */
void create_MG(MGraph *MG) {
    int type, v1, v2, weight;
    char c1, c2;
    
    printf("圖類型 DG(0有向) UDG(1無向): ");
    scanf("%d", &type);
    MG->type = type ? UDG : DG;
    
    printf("頂點數: "); scanf("%d", &MG->vexnum);
    printf("邊數: "); scanf("%d", &MG->arcnum);
    getchar();  // 吸收換行
    
    for (int i = 1; i <= MG->vexnum; i++) {
        printf("第%d個頂點字符: ", i);
        scanf("%c", &MG->vexs[i]);
        getchar();
    }
    
    /* 初始化鄰接矩陣 */
    for (int i = 1; i <= MG->vexnum; i++)
        for (int j = 1; j <= MG->vexnum; j++)
            MG->arcs[i][j] = (i == j) ? 0 : UN_REACH;
    
    /* 輸入邊 */
    for (int k = 1; k <= MG->arcnum; k++) {
        printf("第%d條邊: 起點 終點 權值: ", k);
        scanf("%c %c %d", &c1, &c2, &weight);
        getchar();
        v1 = getIndexOfVexs(c1, MG);
        v2 = getIndexOfVexs(c2, MG);
        if (MG->type == UDG)
            MG->arcs[v1][v2] = MG->arcs[v2][v1] = weight;
        else
            MG->arcs[v1][v2] = weight;
    }
}

/* 打印圖信息 */
void print_MG(MGraph MG) {
    printf("\n圖類型: %s\n", MG.type == DG ? "有向圖" : "無向圖");
    printf("頂點數: %d, 邊數: %d\n", MG.vexnum, MG.arcnum);
    printf("頂點集: ");
    for (int i = 1; i <= MG.vexnum; i++) printf("%c ", MG.vexs[i]);
    printf("\n鄰接矩陣:\n");
    for (int i = 1; i <= MG.vexnum; i++) {
        for (int j = 1; j <= MG.vexnum; j++) {
            if (MG.arcs[i][j] == UN_REACH) printf("∞ ");
            else printf("%d ", MG.arcs[i][j]);
        }
        printf("\n");
    }
}

/* 從鄰接矩陣提取邊數組 */
void init_edge(MGraph MG, Edge edge[]) {
    int count = 0;
    if (MG.type == DG) {  // 有向圖：所有非0、非UN_REACH
        for (int i = 1; i <= MG.vexnum; i++)
            for (int j = 1; j <= MG.vexnum; j++)
                if (MG.arcs[i][j] != 0 && MG.arcs[i][j] != UN_REACH) {
                    edge[count++] = (Edge){i, j, MG.arcs[i][j]};
                }
    } else {  // 無向圖：只取上三角避免重複
        for (int i = 1; i <= MG.vexnum; i++)
            for (int j = i; j <= MG.vexnum; j++)
                if (MG.arcs[i][j] != 0 && MG.arcs[i][j] != UN_REACH) {
                    edge[count++] = (Edge){i, j, MG.arcs[i][j]};
                }
    }
    MG.arcnum = count;  // 實際邊數(無向圖去重後)
}

/* 簡單冒泡排序邊(教學用，工程用qsort) */
void sort_edge(Edge edge[], int arcnum) {
    for (int i = 0; i < arcnum - 1; i++)
        for (int j = i + 1; j < arcnum; j++)
            if (edge[i].cost > edge[j].cost) {
                Edge tmp = edge[i];
                edge[i] = edge[j];
                edge[j] = tmp;
            }
}

/* ===== 并查集核心 ===== */

/* 查找根節點(帶路徑壓縮優化) */
int findFather(int father[], int v) {
    int t = v;
    while (father[t] != -1) t = father[t];
    /* 路徑壓縮：將路徑上所有節點直接指向根 */
    while (v != t) {
        int parent = father[v];
        father[v] = t;
        v = parent;
    }
    return t;
}

/* ===== Kruskal主算法 ===== */
void Kruskal_MG(MGraph MG, Edge edge[]) {
    int father[MAX_VEX_NUM];
    for (int i = 0; i < MAX_VEX_NUM; i++) father[i] = -1;  // -1表示根
    
    int i = 0, count = 0;
    printf("\nKruskal算法構建MST過程:\n");
    
    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;  // 合併集合
            count++;
            printf("選擇邊: %c-%c  權值: %d\n", 
                   MG.vexs[edge[i].start], MG.vexs[edge[i].end], edge[i].cost);
        } else {
            printf("捨棄邊: %c-%c  權值: %d (形成環)\n",
                   MG.vexs[edge[i].start], MG.vexs[edge[i].end], edge[i].cost);
        }
        i++;
    }
    
    if (count == MG.vexnum - 1)
        printf("\nMST構建完成，共 %d 條邊\n", count);
    else
        printf("\n圖不連通，無法構建生成樹\n");
}

/* ===== 主函數 ===== */
int main(void) {
    MGraph MG;
    Edge edge[MAX_ARC_NUM];
    
    create_MG(&MG);
    print_MG(MG);
    init_edge(MG, edge);
    sort_edge(edge, MG.arcnum);
    
    printf("\n排序後邊列表:\n");
    for (int i = 0; i < MG.arcnum; i++)
        printf("%c-%c: %d\n", MG.vexs[edge[i].start], MG.vexs[edge[i].end], edge[i].cost);
    
    Kruskal_MG(MG, edge);
    return 0;
}

運行演示

輸入:
圖類型: 0 (有向)
頂點數: 4
邊數: 5
頂點: a b c d
邊: a b 1
    a c 3
    a d 4
    b c 2
    c d 3

輸出:
排序後邊列表:
a-b: 1
b-c: 2
a-c: 3
c-d: 3
a-d: 4

Kruskal算法構建MST過程:
選擇邊: a-b  權值: 1
選擇邊: b-c  權值: 2
捨棄邊: a-c  權值: 3 (形成環)
選擇邊: c-d  權值: 3
MST構建完成，共 3 條邊

關鍵數據結構：并查集優化

/* 基礎版：僅查找根 */
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]);  // 遞歸壓縮
}

/* 進一步優化：按秩合併(按樹高/尺寸合併) */
int rank[MAX_VEX_NUM] = {0};  // 樹高上界

void unionSets(int father[], int rank[], int x, int y) {
    int rx = findFather(father, x);
    int ry = findFather(father, y);
    if (rx == ry) return;
    if (rank[rx] < rank[ry]) father[rx] = ry;
    else if (rank[rx] > rank[ry]) father[ry] = rx;
    else { father[ry] = rx; rank[rx]++; }
}

Kruskal vs Prim 選型指南

維度KruskalPrim
核心思路邊中心，全局排序點中心，局部擴展
數據結構邊數組 + 并查集優先隊列/最小堆 + 鄰接表
時間複雜度O(E log E)O(E log V) (堆優化)
適合圖類型稀疏圖 (E ≈ V)稠密圖 (E ≈ V²)
邊權重複天然處理需去重或允許重複入堆
並行化排序易並行難並行

工程化注意事項

  • 邊數組大小：無向圖最多V*(V-1)/2條邊，有向圖V*(V-1)
  • 排序穩定性：權值相同時保持原序可用穩定排序，不影響MST正確性
  • 離散圖檢測：算法結束時count < V-1說明圖不連通
  • 最小生成森林：對不連通圖，Kruskal自然產生各連通分量的MST
  • 次小生成樹：在MST基礎上枚舉非樹邊替換樹邊

Kruskal算法以其簡潔優雅的邏輯、優秀的稀疏圖性能、天然的并行化潛力，成為最小生成樹問題的首選方案。掌握并查集的路徑壓縮與按秩合併優化，是解決動態連通性問題的核心技能，廣泛應用於網絡路由、聚類分析、圖像分割等領域。

  1. 上一篇文章：
  2. 下一篇文章：
關於C語言
用 C# Builder 開發資料庫應用程式（一）：環境建置與 ODBC 設定 用 C# Builder 開發資料庫應用程式（一）：環境建置與 ODBC 設定

本文主要介紹用 C# Builder 透過 ODBC 存取資
C# 3.0 入門系列（二） C# 3.0 入門系列（二）

一切準備好後，我們來看這個範例。筆者對 SampleQuer
Objective-C 單例模式完整實現：ARC 與非 ARC 環境雙版本詳解 Objective-C 單例模式完整實現：ARC 與非 ARC 環境雙版本詳解

Objective-C 單例模式完整實現：ARC 與非 AR
撰寫 SQL Server CLR 使用者定義函數（二）：函數實作、部署與測試驗證 撰寫 SQL Server CLR 使用者定義函數（二）：函數實作、部署與測試驗證

Function1.cs 完整程式碼 using Syste
Windows HTTP 協議編程實戰：WinInet API 實現圖片下載完整示例 C語言實作簡易 Shell：命令解析、內建命令與進程創建框架 C# 陣列屬性、foreach 遍歷與交錯陣列vs矩形陣列差異（二） 在 Code::Blocks 中搭建 MSP430 開發環境完整步驟 PC-lint 靜態代碼分析實戰：從入門到 VC6/Source Insight 深度整合 C 語言 MySQL 開發實戰筆記：編譯配置、常見錯誤與最佳實踐 C語言關係運算符與表達式深度解析：優先級、結合性與真值評估
欄目導航
  • C
  • C++
  • VC
  • VC.NET
  • 關於C語言
    • Copyright © 程式碼之家 All Rights Reserved