图的最小生成树：Prim算法、Kruskal算法与并查集实战

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

你可能会问：“这玩意儿有什么用？” 我举个例子。我在做智能电网项目时，需要铺设电缆连接各个变电站。电缆铺得越少，成本越低。这不就是典型的最小生成树问题吗？嗯，今天我们就来啃下这块硬骨头。

一、普里姆（Prim）算法

Prim算法的思路，我个人觉得非常直观。它有点像“贪心扩张”的策略。从一个顶点出发，每次找一条连接“已选顶点集合”和“未选顶点集合”的最短边，把新顶点拉进来。重复这个过程，直到所有顶点都被包含。

我习惯把Prim算法比作“修路队修路”。修路队先占一个村子，然后看哪个邻村离得最近，就把路修过去。新村子加入后，再看所有已通路的村子，哪个邻村最近，继续修。直到所有村子都通路。

Prim算法步骤

1. 任选一个起始顶点，加入生成树集合U。
2. 找出所有连接U中顶点与V-U中顶点的边，选择权值最小的边。
3. 将该边对应的V-U中的顶点加入U。
4. 重复步骤2和3，直到U包含所有顶点。

代码实现（邻接矩阵版）

#define INF 0x3f3f3f3f
#define MAXV 100

// 返回最小生成树的权值和
int prim(int graph[MAXV][MAXV], int n) {
    int lowcost[MAXV];  // 保存各顶点到当前生成树的最小权值
    int closest[MAXV];  // 保存该顶点对应的边在生成树中的另一端点
    int visited[MAXV] = {0};
    int total_weight = 0;

    // 从顶点0开始
    visited[0] = 1;
    for (int i = 1; i < n; i++) {
        lowcost[i] = graph[0][i];
        closest[i] = 0;
    }

    for (int i = 1; i < n; i++) {
        int min = INF;
        int u = -1;

        // 找最小权值边
        for (int j = 0; j < n; j++) {
            if (!visited[j] && lowcost[j] < min) {
                min = lowcost[j];
                u = j;
            }
        }

        if (u == -1) break;  // 图不连通
        visited[u] = 1;
        total_weight += min;

        // 更新lowcost
        for (int j = 0; j < n; j++) {
            if (!visited[j] && graph[u][j] < lowcost[j]) {
                lowcost[j] = graph[u][j];
                closest[j] = u;
            }
        }
    }
    return total_weight;
}

二、克鲁斯卡尔（Kruskal）算法

Kruskal算法是另一种思路。它不看顶点，只看边。把所有边按权值从小到大排序，然后一条一条地选。只要选出来的边不会形成环，就把它加入生成树。

你想想看，这像什么？像不像“拼图”？你手里有一堆长短不一的木条，你要拼一个架子，每次拿最短的木条试，只要不跟已有的木条形成闭环，就装上。直到所有节点都连起来。

Kruskal算法步骤

1. 将图中所有边按权值从小到大排序。
2. 初始化一个空的最小生成树集合T。
3. 遍历排序后的边，如果该边的两个顶点不在同一个连通分量中，则加入T。
4. 重复步骤3，直到T中有n-1条边。

代码实现（边集数组 + 并查集）

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

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

// 并查集查找（带路径压缩）
int find(int parent[], int x) {
    if (parent[x] != x)
        parent[x] = find(parent, parent[x]);
    return parent[x];
}

// 并查集合并
void union_set(int parent[], int rank[], int x, int y) {
    int rx = find(parent, x);
    int ry = find(parent, y);
    if (rx == ry) return;
    if (rank[rx] < rank[ry])
        parent[rx] = ry;
    else if (rank[rx] > rank[ry])
        parent[ry] = rx;
    else {
        parent[ry] = rx;
        rank[rx]++;
    }
}

int kruskal(Edge edges[], int n, int m) {
    qsort(edges, m, sizeof(Edge), cmp);
    int parent[n], rank[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }

    int total_weight = 0;
    int edge_count = 0;

    for (int i = 0; i < m && edge_count < n-1; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        if (find(parent, u) != find(parent, v)) {
            union_set(parent, rank, u, v);
            total_weight += edges[i].w;
            edge_count++;
        }
    }
    return total_weight;
}

三、并查集在Kruskal中的应用

Kruskal算法里最关键的一步是什么？判断两个顶点是否在同一个连通分量中。如果不用并查集，你每次都得遍历一遍当前生成树，看看这两个点是不是已经连上了。那效率太低了。

并查集就是专门干这个的。它能在近乎O(1)的时间里告诉你：“这两个节点是不是一家人？”

我曾经在一个物流配送系统的项目中，需要处理几千个配送点的连通性问题。一开始我用的是DFS遍历判断，结果每次合并都要O(n)时间，整个程序跑起来慢得像蜗牛。后来换成并查集，速度直接起飞。嗯，这就是数据结构的魅力。

并查集核心操作

操作	功能	时间复杂度
find(x)	查找x所属集合的根节点	O(α(n))
union(x, y)	合并x和y所在的集合	O(α(n))

注：α(n)是阿克曼函数的反函数，增长极慢，可以视为常数。

四、Prim vs Kruskal：怎么选？

很多同学会问：“两个算法都能求最小生成树，我该用哪个？” 我的建议是看图的稠密程度。

• 稠密图（边多）： 用Prim。邻接矩阵版O(n²)，堆优化版O((n+m)logn)。边多的时候Prim优势明显。
• 稀疏图（边少）： 用Kruskal。时间复杂度O(mlogm)，主要花在排序上。边少的时候排序很快。

说白了，Prim是“点驱动”，Kruskal是“边驱动”。你根据图的特征选一个就行。

五、知识体系总览

下面这张图，我把本章的核心知识点串起来了。你可以把它当作一张“地图”，学完后再回来看，思路会更清晰。

好了，关于最小生成树的两种经典算法，我们就聊到这里。Prim和Kruskal各有千秋，没有绝对的好坏。关键是你得理解它们的本质，然后在实际项目中灵活选用。下次遇到修路、布线、组网这类问题，你心里就有底了。

---

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