最小生成树：Prim算法、Kruskal算法、经典例题

说到图论里的最小生成树，我脑子里第一个蹦出来的场景是——几年前做城市光缆铺设项目。那时候要在几个新区之间拉光纤，每个节点都得通，但预算卡得死死的。说白了，就是要在所有节点连通的前提下，让总造价最低。这不就是典型的最小生成树问题嘛。

今天咱们就把 Prim 和 Kruskal 这两个算法掰开揉碎。我会结合自己的踩坑经验，把它们的核心逻辑、适用场景、以及代码模板都捋一遍。嗯，保证你学完就能上手。

1. 什么是最小生成树？

一个连通图，有 N 个节点。你从中选出 N-1 条边，让所有节点都连通，并且这 N-1 条边的权重之和最小。这棵树就叫最小生成树（MST）。

你想想看，如果图里有环，那肯定有冗余边。去掉环里最重的那条，总权值就降下来了。所以 MST 的核心就一句话：无环、连通、权值最小。

2. Prim 算法：加点法

我个人习惯把 Prim 叫做「加点法」。它的思路特别直观：从任意一个节点开始，每次找一个离当前树最近的点，把它拉进来。重复直到所有点都在树里。

为什么说它像 Dijkstra？因为两者都用了「松弛」的思想。区别在于：Dijkstra 更新的是到起点的距离，Prim 更新的是到当前树的最小距离。

2.1 算法步骤

1. 选一个起点，加入树
2. 更新所有未加入节点到树的距离
3. 选距离最小的节点加入树
4. 重复 2-3 步，直到所有节点都在树里

2.2 代码模板（邻接矩阵版）

// 返回最小生成树的权值和，n 为节点数，graph 为邻接矩阵
int prim(int n, vector<vector<int>>& graph) {
    vector<int> dist(n, INT_MAX); // 到当前树的最小距离
    vector<bool> visited(n, false);
    dist[0] = 0; // 从节点0开始
    int total = 0;

    for (int i = 0; i < n; ++i) {
        // 找未访问节点中 dist 最小的
        int u = -1;
        int minDist = INT_MAX;
        for (int j = 0; j < n; ++j) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                u = j;
            }
        }
        if (u == -1) return -1; // 图不连通
        visited[u] = true;
        total += minDist;

        // 更新邻居的 dist
        for (int v = 0; v < n; ++v) {
            if (!visited[v] && graph[u][v] < dist[v]) {
                dist[v] = graph[u][v];
            }
        }
    }
    return total;
}

3. Kruskal 算法：加边法

Kruskal 的思路更暴力：把所有边按权重排序，从小到大一条条试。如果这条边连接的两个点还不连通，就把它加进来。直到加了 N-1 条边。

这里的关键是「判断连通性」。我最早用 DFS 每次判断，结果超时到怀疑人生。后来才意识到，并查集才是亲爹。

3.1 算法步骤

1. 把所有边按权重升序排序
2. 初始化并查集，每个节点自成一个集合
3. 遍历排序后的边：如果两个端点不在同一集合，合并集合，加入这条边
4. 当边数达到 N-1 时停止

3.2 代码模板

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

// 并查集
vector<int> parent;
int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}
void unite(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra != rb) parent[ra] = rb;
}

int kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());
    parent.resize(n);
    for (int i = 0; i < n; ++i) parent[i] = i;

    int total = 0, cnt = 0;
    for (auto& e : edges) {
        if (find(e.u) != find(e.v)) {
            unite(e.u, e.v);
            total += e.w;
            cnt++;
            if (cnt == n - 1) break;
        }
    }
    return cnt == n - 1 ? total : -1;
}

4. 两种算法对比

维度	Prim	Kruskal
核心思想	加点	加边
依赖数据结构	优先队列 / 邻接矩阵	并查集
时间复杂度	O(n²) 或 O(m log n)	O(m log m)
适用场景	稠密图	稀疏图
是否依赖起点	是	否

5. 经典例题：连接所有点的最小费用

这是 LeetCode 1584 题。给你一堆点的坐标，两点之间的曼哈顿距离就是边的权重。要你连接所有点，求最小总费用。

说白了，这就是个裸的最小生成树。但有个小坑：如果直接用 Prim，邻接矩阵需要 n² 的空间，n 到 1000 时还能扛。如果 n 到 10⁵，就必须用 Kruskal + 边优化了。

5.1 思路分析

• 计算所有点对之间的曼哈顿距离，生成边列表
• 用 Kruskal 求 MST
• 注意：完全图的边数是 n*(n-1)/2，n 较大时可能超内存。可以优化：只对每个点连接最近的几个点（比如按 x 或 y 排序后连相邻点）

5.2 代码实现（Kruskal 版）

int minCostConnectPoints(vector<vector<int>>& points) {
    int n = points.size();
    vector<Edge> edges;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
            edges.push_back({i, j, dist});
        }
    }
    return kruskal(n, edges);
}

6. 知识体系总览

下面这张图是我自己梳理的 MST 知识框架。你看一眼，心里就有谱了。

7. 写在最后

最小生成树这块，说白了就是两个套路。Prim 像「贪心扩张」，Kruskal 像「贪心筛选」。我个人更偏爱 Kruskal，因为并查集写起来很清爽，而且边排序后还能做其他优化。但遇到稠密图，我会毫不犹豫切回 Prim。

你在刷题时如果遇到「连接所有点」「铺设线路」「网络布线」这类字眼，十有八九就是 MST。先判断图的稠密程度，再选算法，基本不会跑偏。