第十四章：最小生成树——Prim算法、Kruskal算法原理与C语言实现、并查集优化

各位同学，今天我们来聊聊图论里一个非常经典的问题——最小生成树。说白了，就是在一个带权无向连通图里，找一棵树，把所有顶点都连起来，并且所有边的权值之和最小。

我当年刚接触这个算法时，第一反应是：这不就是贪心吗？没错，核心思想就是贪心。但贪心也有不同的贪法。今天我们就讲两种最主流的算法：Prim 和 Kruskal。

一、Prim 算法——从点出发

Prim 算法的思路很直观：从一个顶点开始，每次选择一条连接「已选顶点集合」和「未选顶点集合」的最小权值边，把新顶点加进来。重复直到所有顶点都在集合里。

我习惯把它叫做「点扩展法」。你想想看，就像盖房子，先打一个地基，然后每次找最近的砖头往上垒。

算法步骤

1. 任选一个起始顶点，加入集合 U。
2. 初始化 lowcost 数组，记录 U 中顶点到 V-U 中每个顶点的最小边权。
3. 循环 n-1 次：
   • 在 lowcost 中找到最小值，对应的顶点加入 U。
   • 更新 lowcost：新加入的顶点可能带来更小的边。

C 语言实现（邻接矩阵版）

#define INF 0x3f3f3f3f
#define MAXN 100

int prim(int graph[MAXN][MAXN], int n) {
    int lowcost[MAXN];   // 记录最小边权
    int visited[MAXN];   // 标记是否已加入U
    int total = 0;
    
    // 初始化：从顶点0开始
    for (int i = 0; i < n; i++) {
        lowcost[i] = graph[0][i];
        visited[i] = 0;
    }
    visited[0] = 1;
    
    for (int i = 1; i < n; i++) {
        int min = INF;
        int k = -1;
        
        // 找最小边
        for (int j = 0; j < n; j++) {
            if (!visited[j] && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        
        if (k == -1) return -1; // 图不连通
        
        total += min;
        visited[k] = 1;
        
        // 更新lowcost
        for (int j = 0; j < n; j++) {
            if (!visited[j] && graph[k][j] < lowcost[j]) {
                lowcost[j] = graph[k][j];
            }
        }
    }
    return total;
}

二、Kruskal 算法——从边出发

Kruskal 的思路完全不同：它把所有的边按权值从小到大排序，然后依次尝试加入。如果加入后不形成环，就保留；否则跳过。

说白了，就是「边贪心」。我更喜欢用 Kruskal 处理稀疏图，比如公路网，边数远小于 n² 的情况。

算法步骤

1. 将所有边按权值从小到大排序。
2. 初始化每个顶点为一个独立的集合。
3. 遍历排序后的边：
   • 如果边的两个端点不在同一个集合，就加入这条边，合并两个集合。
   • 否则跳过。
4. 当加入的边数达到 n-1 时停止。

三、并查集优化——Kruskal 的灵魂

并查集是一种树型数据结构，支持两种操作：

• Find：查找元素所属的集合（根节点）。
• Union：合并两个集合。

我刚开始学的时候觉得这玩意儿很简单，不就是数组嘛。但真正写代码时才发现，路径压缩和按秩合并这两个优化，能让效率从 O(n) 降到近乎 O(1)。

并查集的 C 语言实现

#define MAXN 1000

int parent[MAXN];
int rank[MAXN];  // 秩，用于按秩合并

// 初始化：每个元素自成一集
void init(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
}

// 查找：带路径压缩
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // 路径压缩
    }
    return parent[x];
}

// 合并：按秩合并
void unionSet(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    
    if (rootX == rootY) return;
    
    if (rank[rootX] < rank[rootY]) {
        parent[rootX] = rootY;
    } else if (rank[rootX] > rank[rootY]) {
        parent[rootY] = rootX;
    } else {
        parent[rootY] = rootX;
        rank[rootX]++;
    }
}

四、Kruskal 算法的完整 C 语言实现

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

typedef struct {
    int u, v, w;  // 起点、终点、权值
} Edge;

int cmp(const void *a, const void *b) {
    return ((Edge*)a)->w - ((Edge*)b)->w;
}

int kruskal(Edge edges[], int n, int m) {
    // n: 顶点数, m: 边数
    qsort(edges, m, sizeof(Edge), cmp);
    init(n);
    
    int total = 0;
    int count = 0;
    
    for (int i = 0; i < m && count < n-1; i++) {
        int rootU = find(edges[i].u);
        int rootV = find(edges[i].v);
        
        if (rootU != rootV) {
            unionSet(rootU, rootV);
            total += edges[i].w;
            count++;
        }
    }
    
    if (count != n-1) return -1; // 图不连通
    return total;
}

五、两种算法的对比

对比维度	Prim 算法	Kruskal 算法
核心思想	点扩展	边贪心
数据结构	邻接矩阵 / 邻接表	边集数组 + 并查集
时间复杂度	O(n²)（邻接矩阵）	O(m log m)（排序为主）
适用场景	稠密图（边多）	稀疏图（边少）
实现难度	中等	中等（需并查集）

六、一个完整的例子

假设有 4 个顶点，边如下：

• (0,1) 权值 1
• (0,2) 权值 3
• (1,2) 权值 2
• (1,3) 权值 4
• (2,3) 权值 5

用 Kruskal 跑一遍：

1. 排序后：(0,1,1), (1,2,2), (0,2,3), (1,3,4), (2,3,5)
2. 加入 (0,1)：集合 {0,1}
3. 加入 (1,2)：集合 {0,1,2}
4. 检查 (0,2)：0和2已在同一集合，跳过
5. 加入 (1,3)：集合 {0,1,2,3}，边数达到 3，结束

最小权值和 = 1 + 2 + 4 = 7。

嗯，这个例子很简单，但能帮你理解算法的执行流程。我当年就是靠手算这种小例子，才真正搞懂 Kruskal 的。

---

公众号:蓝海资料掘金营，微信deep3321