每日算法 — 使用java实现Kruskal算法：贪心策略与并查集构建最小生成树

最小生成树（Minimum Spanning Tree, MST）是图论中的经典问题：给定一个带权无向连通图，找出一棵包含所有顶点的树，使得树上所有边的权值之和最小。Kruskal 算法是解决该问题最优雅的算法之一，其核心思想是贪心选择边权最小的边，同时用并查集避免成环。本文将完整实现 Kruskal 算法，并通过”城市通信网络建设”场景展示其应用。

算法思想

Kruskal 算法的执行步骤如下：

1. 将图中所有边按权值从小到大排序。
2. 依次遍历每条边，若该边连接的两个顶点不在同一连通分量中（即加入后不形成环），则将其加入生成树。
3. 重复步骤 2，直到生成树中包含 V-1 条边（V 为顶点数）。

为什么贪心策略是正确的？
这是典型的贪心算法正确性证明——切割性质（Cut Property）：对于图的任意一个切割，跨越切割的最小权边一定属于某棵最小生成树。Kruskal 每次选择全局最小边且不形成环，本质上就是在不断寻找合法的切割最小边。

并查集（Union-Find）

并查集是 Kruskal 算法的核心辅助结构，用于高效判断两个顶点是否连通：

• Find：查找某个元素所属的集合（根节点）。
• Union：合并两个集合。
• 路径压缩：在 Find 时将被查节点直接挂到根下，加速后续查询。
• 按秩合并：合并时将小树挂到大树下，控制树高。

/**
 * 并查集实现：支持路径压缩与按秩合并
 */
public class UnionFind {
    private final int[] parent;
    private final int[] rank;
    private int count; // 连通分量数量

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    /**
     * 查找根节点，同时进行路径压缩
     */
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 递归路径压缩
        }
        return parent[x];
    }

    /**
     * 合并两个集合，按秩合并
     * @return 是否成功合并（原本不在同一集合）
     */
    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return false; // 已在同一集合，合并会形成环

        // 将小树挂到大树下
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        count--;
        return true;
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    public int getCount() {
        return count;
    }
}

Kruskal 算法完整实现

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 带权边
 */
public class Edge implements Comparable<Edge> {
    private final int from;
    private final int to;
    private final int weight;

    public Edge(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.weight, other.weight);
    }

    @Override
    public String toString() {
        return String.format("Edge(%d-%d, w=%d)", from, to, weight);
    }

    public int getFrom() { return from; }
    public int getTo() { return to; }
    public int getWeight() { return weight; }
}

/**
 * Kruskal 最小生成树算法
 */
public class KruskalMST {

    /**
     * 计算最小生成树
     * @param n 顶点数量（编号 0 到 n-1）
     * @param edges 图中的所有边
     * @return 最小生成树的边集合，若图不连通则返回null
     */
    public static List<Edge> findMST(int n, List<Edge> edges) {
        // 1. 按边权升序排序
        Collections.sort(edges);

        UnionFind uf = new UnionFind(n);
        List<Edge> mst = new ArrayList<>();
        int totalWeight = 0;

        // 2. 依次考察每条边
        for (Edge edge : edges) {
            // 若该边连接的两个顶点不连通，则加入MST
            if (uf.union(edge.getFrom(), edge.getTo())) {
                mst.add(edge);
                totalWeight += edge.getWeight();
                System.out.println("选中: " + edge + "，当前总权值: " + totalWeight);

                // 当选中 n-1 条边时，MST构建完成
                if (mst.size() == n - 1) {
                    break;
                }
            } else {
                System.out.println("跳过: " + edge + "（会形成环）");
            }
        }

        // 检查图是否连通
        if (mst.size() != n - 1) {
            System.out.println("图不连通，无法构建最小生成树！");
            return null;
        }

        System.out.println("\n最小生成树构建完成！总权值: " + totalWeight);
        return mst;
    }

    public static void main(String[] args) {
        int n = 6; // 6个顶点
        List<Edge> edges = new ArrayList<>();

        // 构建一个示例图（城市间通信线路及成本）
        edges.add(new Edge(0, 1, 4)); // A-B: 4
        edges.add(new Edge(0, 2, 3)); // A-C: 3
        edges.add(new Edge(1, 2, 1)); // B-C: 1
        edges.add(new Edge(1, 3, 2)); // B-D: 2
        edges.add(new Edge(2, 3, 4)); // C-D: 4
        edges.add(new Edge(3, 4, 2)); // D-E: 2
        edges.add(new Edge(4, 5, 6)); // E-F: 6
        edges.add(new Edge(2, 4, 5)); // C-E: 5
        edges.add(new Edge(2, 5, 7)); // C-F: 7

        System.out.println("===== Kruskal 算法执行过程 =====\n");
        List<Edge> mst = findMST(n, edges);

        System.out.println("\n===== 最小生成树的边 =====");
        if (mst != null) {
            for (Edge e : mst) {
                System.out.println(e);
            }
        }
    }
}

实战应用：城市通信网络建设

假设你需要为一个地区的6座城市铺设光纤通信网络，每两座城市之间可以铺设线路，但成本不同。目标是让所有城市互相连通，且总铺设成本最低：

/**
 * 城市通信网络规划系统
 */
public class CityNetworkPlanner {

    private final String[] cityNames;
    private final List<Edge> possibleLinks;

    public CityNetworkPlanner(String[] cityNames) {
        this.cityNames = cityNames;
        this.possibleLinks = new ArrayList<>();
    }

    public void addPossibleLink(int cityA, int cityB, int cost) {
        possibleLinks.add(new Edge(cityA, cityB, cost));
    }

    public void planNetwork() {
        System.out.println("===== 城市通信网络规划 =====");
        System.out.println("目标城市: " + String.join(", ", cityNames));
        System.out.println("\n可选线路及成本:");
        for (Edge e : possibleLinks) {
            System.out.printf("  %s <-> %s : %d 万元%n",
                cityNames[e.getFrom()], cityNames[e.getTo()], e.getWeight());
        }

        System.out.println("\n===== 开始规划 =====\n");
        List<Edge> mst = KruskalMST.findMST(cityNames.length, new ArrayList<>(possibleLinks));

        if (mst != null) {
            System.out.println("\n===== 最优铺设方案 =====");
            int totalCost = 0;
            for (Edge e : mst) {
                System.out.printf("铺设 %s <-> %s 线路，成本 %d 万元%n",
                    cityNames[e.getFrom()], cityNames[e.getTo()], e.getWeight());
                totalCost += e.getWeight();
            }
            System.out.println("\n预计最低总成本: " + totalCost + " 万元");
        }
    }

    public static void main(String[] args) {
        String[] cities = {"北京", "上海", "广州", "深圳", "杭州", "成都"};
        CityNetworkPlanner planner = new CityNetworkPlanner(cities);

        // 添加可选线路（单位：万元）
        planner.addPossibleLink(0, 1, 1200); // 北京-上海
        planner.addPossibleLink(0, 2, 1800); // 北京-广州
        planner.addPossibleLink(1, 2, 1300); // 上海-广州
        planner.addPossibleLink(1, 3, 1400); // 上海-深圳
        planner.addPossibleLink(2, 3, 800);  // 广州-深圳
        planner.addPossibleLink(2, 4, 900);  // 广州-杭州
        planner.addPossibleLink(3, 4, 1100); // 深圳-杭州
        planner.addPossibleLink(3, 5, 1500); // 深圳-成都
        planner.addPossibleLink(4, 5, 1000); // 杭州-成都
        planner.addPossibleLink(0, 5, 1600); // 北京-成都

        planner.planNetwork();
    }
}

Kruskal vs Prim 对比

进阶：最大生成树与次小生成树

只需稍作修改，Kruskal 算法就能求解最大生成树：

// 将边按降序排序即可求最大生成树
Collections.sort(edges, Collections.reverseOrder());

次小生成树的求解思路：先求出 MST，然后枚举不在 MST 中的每条边，将其加入 MST（会形成环），再删除环上除该边外的最大边，取所有结果中权值最小者。

/**
 * 次小生成树求解框架
 */
public class SecondMST {
    public static List<Edge> findSecondMST(int n, List<Edge> edges, List<Edge> mst) {
        int mstWeight = mst.stream().mapToInt(Edge::getWeight).sum();
        int secondMstWeight = Integer.MAX_VALUE;
        List<Edge> secondMST = null;

        for (Edge e : edges) {
            if (mst.contains(e)) continue; // 跳过已在MST中的边

            // 将非树边加入MST，会形成环
            // 实际实现需要找到环上的最大边并用e替换
            // 此处为简化示意
        }
        return secondMST;
    }
}

复杂度分析

其中 (\alpha) 为阿克曼函数的反函数，增长极其缓慢，可视为常数。

总结

Kruskal 算法以其简洁的贪心策略和并查集的高效支持，成为求解最小生成树的首选方法之一。从理论上看，切割性质保证了贪心选择的正确性；从工程上看，排序加并查集的组合易于实现且性能优异。无论是通信网络规划、电路板布线还是集群架构设计，最小生成树的思想都在背后发挥着重要作用。