本文介绍了图论中的另一个经典问题：最小生成树（MST），讲解并用 Java 实现了用于求解 MST 的两个经典算法 Prim 与 Kruskal。

1. 最小生成树介绍

最小生成树（Minimum Spanning Tree，MST）是图论中的一个经典问题，针对一个带权无向连通图，目标是找到一个边的子集，使得：

• 所有顶点均被连接（形成一棵树，即无环且连通）；
• 所有边的权重之和最小。

MST 具有几个关键性质：

• 边数：对于 $n$ 个顶点的图，MST 包含 $n-1$ 条边。
• 无环性：MST 是一棵树，因此不存在环路。
• 不唯一性：如果图中存在多条权重相同的边，可能存在多个不同的 MST。

MST 一般适用于网络设计（如用最小成本连接所有路由器）、电路布线（最小化导线总长度）、聚类分析（如合并相似数据点）等场景。

求解 MST 的算法类似上一节课中的 Dijkstra，均基于贪心策略，每次选择局部最优解。但 MST 是全局优化，关注连接所有顶点的最小总成本，例如可以说在一个图中求出他的最小生成树；而 Dijkstra 是局部优化，关注从某个起点到每个顶点的最小路径成本，我们不能说是在一个图中求出他的最短路径树，因为只有确定了起点才能求最短路径。

下图展示了最短路径树（左）与最小生成树（右）的区别：

在最小生成树中我们选择了 (1, 2) 这条边，因为在最短路径中所选择的 (0, 2) 权值大于 (1, 2)，而这两条边无论连接哪一条都能使整个图连通起来，因此显然 (1, 2) 更合适，这样最后的总开销会更小。

如果在最短路径中选择了 (1, 2) 这条边，那么节点 2 的最短距离为 2 + 5 = 7，因为最短路径要考虑的是到起点的距离，也就是到起点的路径上所有的边都会对最短距离产生影响，因为起点是 0 所以我们如果连接 (1, 2) 就必须要考虑 (0, 1)，但最小生成树则不用考虑这些，我们选择的每条边都可以看成是独立的选择，我们选择 (1, 2) 只用考虑这条边对最后总成本的影响。

2. 切割性质

切割（Cut）表示将图的顶点集 $V$ 分割为两个非空不相交的子集 $S$ 与 $V/S$，交叉边即为连接 $S$ 与 $V/S$ 的边。

切割性质（Cut Property）是 MST 的核心理论之一，它描述了在图的任意一个切割中，权重最小的交叉边必然属于某个最小生成树。

如下图所示，我们将所有顶点分为白色和绿色两个集合，粉色的边即表示切割交叉边：

在构建最小生成树的过程中我们会在每一步中选择当前切割中的最小边，确保最终总权重最小，若放弃当前切割的最小边，则后续还想将这两个子集相连就必须用更大的边代替，总权重必然更大。

3. Prim

Prim 算法的核心思想是逐步扩展一棵树，从任意一个顶点开始，每次选择一条连接已选顶点集合（即最小生成树的顶点集合）和未选顶点集合的最小权重边，将新顶点加入已选集合，直到覆盖所有顶点。我们可以维护一个优先队列（最小堆），始终选择当前能连接到最小生成树的最小边。因此 Prim 算法的时间复杂度为 $O(m+nlogn)$，$n$、$m$ 分别表示顶点数和边数。

Prim 算法流程如下：

• 初始化：随机选择一个顶点作为起点，将其加入生成树集合，设置起点到生成树集合的距离 dis[start] = 0，其余顶点的距离为无穷大；初始化一个用来标记是否已经加入集合的数组 vis[] = false；初始化 res = 0, cnt = 0 分别用来记录最小生成树的总权值以及加入到生成树集合的节点数。
• 维护优先队列：将 {dis[start], start} 加入到优先队列中，队列按首元素从小到大排序。
• 队列不为空时循环：
  • 取出队头顶点 u 与其距离 dis[u]，若该点已在集合中则跳过本次循环，否则标记 vis[u] = true，并将该点到集合的距离累加到总权值上：res += dis[u]，然后生成树集合的节点数加一：cnt += 1；
  • 遍历 u 的所有邻边 (u <-> v, w)，判断 v 到集合的最短距离是否能被更新，如果 w < dis[v] 说明这条边能用来更新 v 到集合的最短距离，只要最短距离能被更新的点一定还没加入到集合中，因此将 v 加入优先队列。
• 判断是否形成最小生成树：若最后集合中的节点数不等于图的总节点数说明不连通，不存在最小生成树。

现在来画图演示一遍 Prim 算法的流程，我们可以任意选择一个起始点加入队列，默认就选择 0，将其到集合的距离设为 0，其余节点到集合的距离为无穷大：

从队列中取出距离集合最近的点，目前只有 0，从队列取出的顶点一定是当前离集合最近的点之一，因此将其加入集合中（标记 vis 为 true），此时 res = 0, cnt = 1，然后用 0 更新所能到达的其他点距离集合的最短距离，也就是需要更新 1 和 2：

接下来离集合最近的点是 1，从第二个点加入集合开始就表示集合中多连了一条新的边，这条边的长度就是新加入的点与集合之间的最小距离，即 dis[1]，需要累加到最小生成树的总权值中，我们将 1 加入集合后同样更新一遍其他点到集合之间的最短距离：

之后的流程与前面一样，下一步要加入集合的应该是 2，然后需要更新 dis[4]，因为 4 < 7，有更近的路径可以连接到集合中：

接下来加入集合的是 4：

最后是 3，结束 Prim 算法：

结束后检查 cnt 等于图的节点数，说明每个节点都已经加入到最小生成树的集合中，也就是存在最小生成树，其权值为 13。

Java 实现 Prim 算法代码如下：

package CS61B.Lecture25;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.stream.IntStream;

public class WeightedGraph {
    private record Edge(int to, int weight) {}  // 用来构建邻接表的边

    private final int V;
    private final ArrayList<LinkedList<Edge>> adj;  // 邻接表

    public WeightedGraph(int v) {
        V = v;
        adj = new ArrayList<>();
        for (int i = 0; i < v; i++)
            adj.add(new LinkedList<>());
    }

    /** 添加无向边 (u, v, w) */
    public void addEdge(int u, int v, int w) {
        adj.get(u).add(new Edge(v, w));
        adj.get(v).add(new Edge(u, w));
    }

    /** Prim 算法求解最小生成树 */
    public int prim() {
        int[] dis = IntStream.generate(() -> 0x3f3f3f3f).limit(V).toArray();
        boolean[] vis = new boolean[V];
        PriorityQueue<int[]> Q = new PriorityQueue<>(Comparator.comparingInt(x -> x[0]));

        dis[0] = 0;
        Q.offer(new int[]{dis[0], 0});
        int res = 0, cnt = 0;

        while (!Q.isEmpty()) {
            int u = Q.poll()[1];
            if (vis[u]) continue;  // 已在集合中则跳过
            vis[u] = true;
            res += dis[u];
            cnt++;
            for (Edge e : adj.get(u))
                if (e.weight < dis[e.to]) {
                    dis[e.to] = e.weight;
                    Q.offer(new int[]{dis[e.to], e.to});  // 只要距离还能更新一定还没被加入到集合中
                }
        }

        if (cnt != V) System.out.println("不存在最小生成树");
        return res;
    }

    /** 测试 */
    public static void main(String[] args) {
        WeightedGraph g = new WeightedGraph(5);
        g.addEdge(0, 1, 2);
        g.addEdge(0, 2, 6);
        g.addEdge(1, 2, 5);
        g.addEdge(1, 3, 11);
        g.addEdge(1, 4, 7);
        g.addEdge(2, 4, 4);
        g.addEdge(3, 4, 2);
        System.out.println(g.prim());  // 13
    }
}

4. Kruskal

Kruskal 算法也是一种贪心算法，核心思想是按边权重从小到大排序，依次选择边加入生成树，若该边连接的两个顶点不在同一连通分量中（避免环），则加入。Kruskal 算法高效的关键是使用了并查集（在 Lecture 14 中讲解）来高效地判断两个顶点是否连通，时间复杂度为 $O(mlogm)$。

Kruskal 算法流程如下：

• 排序边：将所有边按权重从小到大排序。
• 初始化并查集：每个顶点初始为一个独立的集合。
• 按权重从小到大遍历每条边 (u <-> v, w)，若边的两个顶点属于不同集合，即 find(u) != find(v)，则将该边加入生成树，然后合并两个顶点所在的集合：union(u, v)。
• 终止条件：当生成树包含 $n-1$ 条边时停止。

Kruskal 相比 Prim 会更好理解一点，而且其性能一般还更优秀，接下来我们画图演示一下 Kruskal 算法的流程，首先初始化将所有边按权重从小到大排好序，然后初始化两个变量 res = 0, cnt = 0，分别用来表示生成树的总权重以及生成树的总边数：

首先判断第一条边的两个顶点 0 和 1 未在一个连通的集合中，因此这条边加入到生成树中，两个顶点用并查集合并成一个集合：

下一条边同理，也是两个不再同一集合中的顶点，合并顶点然后将这条边加入生成树，但是注意此时 {3, 4} 是一个与 {1, 2} 不同的集合，只是各自连通了但是这两个集合之间还没连通：

接下来同理，把 2 加入到 {3, 4} 集合中：

接下来的边 (2, 4) 所连接的两个顶点已经在同一个集合中了，如果还把这条边加进来那就会形成环，因此这条边跳过不处理：

最后连接 1 和 2，此时生成树的边数已经为 $n-1$，说明已经形成最小生成树了，结束 Kruskal 算法：

Java 实现 Kruskal 算法代码如下：

package CS61B.Lecture25;

import CS61B.Lecture14.DisjointSetUnion;

import java.util.*;

public class WeightedGraph {
    private record Edge(int u, int v, int w) {}  // 用来构建边表的边

    private final int V;
    private final ArrayList<Edge> edges;  // 边表

    public WeightedGraph(int v) {
        V = v;
        edges = new ArrayList<>();
    }

    /** 添加无向边 (u, v, w) */
    public void addEdge(int u, int v, int w) {
        edges.add(new Edge(u, v, w));
    }

    /** Kruskal 算法求解最小生成树 */
    public int kruskal() {
        edges.sort(Comparator.comparingInt(x -> x.w));  // 根据边的权值从小到大排序
        DisjointSetUnion dsu = new DisjointSetUnion(V);  // Lecture 14 中实现的并查集
        int res = 0, cnt = 0;  // 分别表示生成树的总权值与生成树的总边数

        for (Edge e : edges) {
            if (dsu.isConnected(e.u, e.v)) continue;
            dsu.union(e.u, e.v);
            res += e.w;
            cnt++;
            if (cnt == V - 1) break;
        }

        if (cnt != V - 1) System.out.println("不存在最小生成树");
        return res;
    }

    /** 测试 */
    public static void main(String[] args) {
        WeightedGraph g = new WeightedGraph(5);
        g.addEdge(0, 1, 2);
        g.addEdge(0, 2, 6);
        g.addEdge(1, 2, 5);
        g.addEdge(1, 3, 11);
        g.addEdge(1, 4, 7);
        g.addEdge(2, 4, 4);
        g.addEdge(3, 4, 2);
        System.out.println(g.kruskal());  // 13
    }
}