第16章 图的最小生成树：Prim算法与Kruskal算法

聊到图的最小生成树，我得先说说自己的经历。刚入行那会儿，我在一家通信公司做网络规划。老板丢给我一张城市节点图，说：「把这些基站用光纤连起来，成本最低。」我当时就懵了——几十个节点，手动算？后来才知道，这就是典型的最小生成树问题。

说白了，最小生成树就是在一个带权无向连通图中，找一棵树，把所有顶点都连起来，并且边的总权重最小。嗯，这里要注意：树意味着没有环，而且恰好有 n-1 条边（n 是顶点数）。

解决这个问题，有两个经典算法：普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。今天咱们就把它们彻底讲透。

一、Prim 算法：从顶点开始「生长」

Prim 算法的思路很直观。你想象一下：随便选一个顶点作为起点，然后每次找一条「连接已选顶点和未选顶点」的最短边，把那个新顶点加进来。重复直到所有顶点都被选中。

我个人习惯用优先队列（最小堆）来实现 Prim。为什么呢？因为每次找最小边的时候，堆能帮我们 O(log n) 搞定，比暴力扫描快太多了。

// Prim 算法实现（邻接矩阵版）
#define INF 0x3f3f3f3f
#define MAXN 1005

int prim(int graph[MAXN][MAXN], int n) {
    int dist[MAXN];      // 到已选集合的最小距离
    int visited[MAXN] = {0};
    int total_weight = 0;
    
    // 初始化：从顶点0开始
    for (int i = 0; i < n; i++) {
        dist[i] = graph[0][i];
    }
    visited[0] = 1;
    
    for (int i = 1; i < n; i++) {
        // 找距离最小的未访问顶点
        int min_dist = INF;
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                u = j;
            }
        }
        
        if (u == -1) return -1;  // 图不连通
        total_weight += min_dist;
        visited[u] = 1;
        
        // 更新距离
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] < dist[v]) {
                dist[v] = graph[u][v];
            }
        }
    }
    return total_weight;
}

二、Kruskal 算法：从边开始「拼接」

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

你想想看，这里最关键的问题是什么？如何快速判断加入一条边会不会形成环？答案是用并查集（Union-Find）。这是我特别喜欢的一个数据结构，代码短、效率高。

// 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], rank[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) 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) {
    // 初始化并查集
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
    
    qsort(edges, m, sizeof(Edge), cmp);
    
    int total_weight = 0;
    int edge_count = 0;
    
    for (int i = 0; i < m && edge_count < 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_weight += w;
            edge_count++;
        }
    }
    
    if (edge_count != n-1) return -1;  // 图不连通
    return total_weight;
}

三、两种算法的对比与选择

好了，两个算法都讲完了。你可能会问：到底该用哪个？

我直接给你一个结论：

对比维度	Prim 算法	Kruskal 算法
核心思想	加点法	加边法
数据结构	优先队列 / 数组	并查集 + 排序
时间复杂度	O(n²) 或 O(E log V)	O(E log E)
适合场景	稠密图（边多）	稀疏图（边少）
实现难度	中等	较低（代码更短）
空间复杂度	O(n) 或 O(n²)	O(E)

我的选择原则很简单：

• 如果图是稠密图（比如完全图），用 Prim 的 O(n²) 版本，省去排序开销。
• 如果图是稀疏图（边数接近顶点数），用 Kruskal，代码好写，而且并查集效率极高。
• 如果图特别大（顶点上万），我倾向用堆优化的 Prim，因为 Kruskal 的排序可能成为瓶颈。

四、实战中的避坑指南

最后分享几个我亲身经历过的坑：

1. 图不连通怎么办？两个算法都要检测。Prim 里如果 dist 数组全是 INF，说明图不连通。Kruskal 里如果最后边数不到 n-1，也是不连通。别傻傻地返回一个错误的最小生成树。
2. 权重相等的情况。如果有多条边权重相同，随便选哪条都可以。但要注意：不同的选择可能得到不同的树，但总权重是一样的。
3. 负权边。最小生成树允许负权边，两个算法都能处理。但如果你遇到负权环，那就不属于最小生成树的范畴了——那是最短路径的问题。
4. 内存爆炸。用邻接矩阵存 10000 个顶点的图，光矩阵就要 400MB。我建议用邻接表，尤其是 Kruskal，只需要存边列表。

嗯，关于最小生成树，今天就聊到这儿。这两个算法是图论里的基本功，理解了它们，后面学最短路径、网络流都会轻松很多。你可以在自己的项目里试试，比如规划布线、设计电路板，都能用上。

---