最小生成树：Prim 与 Kruskal

“最小生成树：Prim 与 Kruskal”这一块，我曾经有一种很典型的错觉：内容看懂了，自己也会了。我真正关掉答案后才发现：最小生成树最开始被我和最短路径混为一谈，都是“找最短的边”，目标其实完全不一样。后来我用画图、手算和最小代码反复验证，才把表面的熟悉变成可以复述的理解。

最小生成树解决的是连接成本问题：给定一个无向连通加权图，选择一些边，让所有点连通，并且总权重最小。

它和最短路很容易混淆。最短路关心从一个点到另一个点的路径最短；最小生成树关心把所有点连接起来的总成本最小。

它从哪里来

最小生成树研究与低成本电网、通信网设计密切相关。Borůvka 在 1926 年研究电力网络时就提出相关算法，随后 Jarník、Prim 与 Kruskal 分别形成经典方法。它优化的是连接全部节点的总成本，不是任意两点最短路。

Prim 和 Kruskal

图：Prim 从点集合向外扩，Kruskal 从边集合里挑不会成环的最小边

两个经典算法：

• Prim：从一个点出发，不断选择连接当前集合和外部点的最小边。
• Kruskal：把所有边按权重排序，依次选择不会形成环的边。

Kruskal

Kruskal 非常适合和并查集配合。

int kruskal(int n, int[][] edges) {
    Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));
    UnionFind uf = new UnionFind(n);
    int cost = 0, used = 0;
    for (int[] e : edges) {
        int u = e[0], v = e[1], w = e[2];
        if (uf.union(u, v)) {
            cost += w;
            used++;
            if (used == n - 1) break;
        }
    }
    if (used != n - 1) throw new IllegalStateException("graph is not connected");
    return cost;
}

如果一条边连接的两个点已经在同一集合里，加入它会形成环，所以跳过。

复杂度主要来自边排序：O(E log E)。

Prim

Prim 更像 Dijkstra：维护当前已连接点集合，每次选择一条最小边扩展出去。

int prim(List<List<int[]>> graph) {
    int n = graph.size();
    boolean[] visited = new boolean[n];
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    pq.offer(new int[]{0, 0});
    int cost = 0, count = 0;
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int u = cur[0], w = cur[1];
        if (visited[u]) continue;
        visited[u] = true;
        cost += w;
        count++;
        for (int[] e : graph.get(u)) {
            if (!visited[e[0]]) pq.offer(e);
        }
    }
    if (count != n) throw new IllegalStateException("graph is not connected");
    return cost;
}

堆优化 Prim 的复杂度通常是 O(E log V)。

什么时候用哪个

正确性直觉

最小生成树有一个重要性质：割性质。

把图的点分成两个集合，跨越这两个集合的最小边，一定可以出现在某棵最小生成树中。Prim 和 Kruskal 都是在利用这个性质，只是一个从点集合扩展，一个从全局最小边选择。

工程场景

• 网络布线成本最小化。
• 多个机房之间的连接规划。
• 城市道路或管线建设。
• 聚类算法中的层次聚类。
• 游戏地图、关卡连接。

工程里要注意：现实网络可能有容量、可靠性、冗余和权限要求，不一定只追求最小总成本。最小生成树给的是成本最低连通方案，但不是最高可用方案。

常见错误

• 把有向图直接套最小生成树。
• 图不连通时仍返回结果。
• Kruskal 没有判断成环。
• Prim 重复加入已访问节点，导致成本重复计算。
• 把最短路和最小生成树混为一谈。

面试题

1. 最短路和最小生成树有什么区别？
2. Kruskal 为什么需要并查集？
3. Prim 和 Dijkstra 为什么看起来相似？区别是什么？
4. 图不连通时最小生成树是否存在？
5. 什么是割性质？

小结

最小生成树不是找两点之间最短，而是用最小总成本连通全部点。Kruskal 站在边的视角，Prim 站在点集合扩展的视角。理解这个区别，图算法的很多概念会清晰很多。