最小生成树：普里姆与克鲁斯卡尔算法

说到图论里的最小生成树，我脑子里第一个蹦出来的场景是——几年前给一个智能仓储系统做路径规划。仓库里几十个货架要布线，既要连起来，又得省线材。说白了，就是在一个连通图里找一棵树，把所有顶点都连上，而且边的总权重最小。这就是最小生成树（MST）要干的事。

今天咱们聊两个经典算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。它们思路不同，但都能搞定MST。我个人习惯是：稠密图用Prim，稀疏图用Kruskal。为什么？往下看你就明白了。

1. 普里姆算法：从点出发，慢慢长

Prim算法的思路特别像“滚雪球”。从一个起点开始，每次找离当前“雪球”最近的那个顶点，把它拉进来。直到所有顶点都进圈。

我当年第一次学这个算法时，觉得它跟Dijkstra最短路径长得太像了。确实，都是贪心，都是维护一个距离数组。但区别在于：Dijkstra更新的是到起点的距离，Prim更新的是到当前生成树的距离。

算法步骤

  1. 选一个起点，加入生成树集合U。
  2. 维护一个数组lowcost，记录每个顶点到U的最短边权。
  3. 每次从U外选lowcost最小的顶点，加入U。
  4. 更新新顶点邻居的lowcost。
  5. 重复直到U包含所有顶点。

核心要点：Prim算法每次只关心“当前树”和“外部顶点”之间的最短边。它不关心外部顶点之间怎么连。

代码实现（邻接矩阵版）

#define INF 0x3f3f3f3f
#define MAXN 100

int prim(int graph[MAXN][MAXN], int n) {
    int lowcost[MAXN];  // 到生成树的最小权值
    int visited[MAXN] = {0};
    int total = 0;

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

    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) return -1; // 图不连通
        visited[u] = 1;
        total += min;

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

我的小经验：用邻接矩阵实现Prim时，时间复杂度是O(n²)。如果图比较稠密（边数接近n²），这个效率其实不错。我曾经在一个城市交通规划项目里用Prim处理了2000个节点的稠密图，跑起来挺顺的。

2. 克鲁斯卡尔算法：从边出发，慢慢挑

Kruskal的思路跟Prim完全不同。它不看点，只看边。把所有边按权重从小到大排序，然后一条一条试。如果这条边连接的两个顶点还没连通，就把它加进来。这里的关键是——怎么判断两个顶点是否已经连通？答案是并查集。

嗯，这里要注意：Kruskal算法里并查集是灵魂。我刚开始写的时候，忘了路径压缩，结果在大图上跑得巨慢。后来加上路径压缩，速度直接起飞。

算法步骤

  1. 把所有边按权值从小到大排序。
  2. 初始化并查集，每个顶点自成一个集合。
  3. 从小到大遍历每条边(u, v, w)：
    • 如果find(u) != find(v)，说明u和v还没连通，加入这条边，合并集合。
    • 否则跳过。
  4. 当加入的边数达到n-1时，结束。

核心要点：Kruskal算法是“全局贪心”，每次选当前最小的边。它不关心树长什么样，只关心边够不够小、会不会形成环。

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

typedef struct {
    int u, v, w;
} Edge;

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

int parent[MAXN];

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

void union_set(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx != ry) parent[rx] = ry;
}

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

    int total = 0, cnt = 0;
    for (int i = 0; i < m && cnt < n-1; i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        if (find(u) != find(v)) {
            union_set(u, v);
            total += w;
            cnt++;
        }
    }
    return cnt == n-1 ? total : -1;
}

避坑指南：我曾经在Kruskal里忘了对边排序，结果跑出来一个乱七八糟的树。还有一次并查集没初始化，直接段错误。记住：排序是前提，并查集初始化是必须的。

3. 两种算法对比

对比项 普里姆（Prim） 克鲁斯卡尔（Kruskal）
核心思想 点扩展 边选择
数据结构 邻接矩阵/邻接表 边集数组 + 并查集
时间复杂度 O(n²)（邻接矩阵）
O(m log n)（堆优化）		 O(m log m)
适用场景 稠密图 稀疏图
是否依赖起点 是 否

你想想看，如果图里边的数量特别多，比如接近完全图，那Kruskal光排序就要花不少时间。而Prim用邻接矩阵直接扫，反而更快。反过来，如果图很稀疏，边数跟顶点数差不多，那Kruskal的排序成本就低了，而且并查集操作几乎常数时间。

4. 知识体系总览

下面这张图把两个算法的核心逻辑串起来了。我画的时候特意把“贪心”放在中间，因为两个算法本质上都是贪心——只是贪心的对象不同。

最小生成树（MST） 贪心策略 普里姆（Prim） 克鲁斯卡尔（Kruskal） 从点出发，每次选最近顶点 数据结构：邻接矩阵 / 堆 适用：稠密图 从边出发，每次选最小边 数据结构：边集 + 并查集 适用：稀疏图

5. 实际项目中的选择

我记得有一次做物联网网关的固件开发，需要给一组传感器节点规划通信链路。节点之间距离近的可以直连，远的得中继。图大概有500个节点，边数大概3000条——算稀疏图。我直接上了Kruskal，排序加并查集，跑下来不到10毫秒。

另一个项目是芯片内部模块的时钟树布线。模块之间几乎全连接，边数接近n²/2。这种稠密图我用Prim的邻接矩阵版，O(n²)的复杂度完全扛得住。如果用Kruskal，光排序O(m log m)就比Prim慢不少。

我的建议：别死记硬背“稠密用Prim，稀疏用Kruskal”。你可以在代码里加个判断：如果m > n * log2(n)，用Prim；否则用Kruskal。这个经验公式我用了好几年，挺稳的。

好了，最小生成树的两种经典算法就聊到这儿。Prim像种树，从一棵苗慢慢长成一片林；Kruskal像拼图，从最小的碎片开始拼。两种思路都值得好好消化。下次你遇到布线、组网、聚类之类的问题，不妨想想——这背后是不是一个最小生成树问题？

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

← 上一章 📖 返回目录 下一章 →