克鲁斯卡尔（Kruskal）算法生成最小生成树(MST)原理及算法实现

一、目的

本实验旨在理解和掌握克鲁斯卡尔（Kruskal）算法的基本原理，并通过编程实现该算法，以求解给定无向加权图的最小生成树。通过本实验，能够加深对最小生成树概念的理解，并提升编程能力。

二、原理

克鲁斯卡尔算法是一种求解最小生成树的贪心算法。其基本原理是：首先，将所有边按照权重从小到大进行排序；然后，从权重最小的边开始，如果这条边连接的两个顶点不在同一个集合中（即不构成环），则将其加入最小生成树中，并将这两个顶点所在的集合合并；重复这个过程，直到选择了n-1条边（n为顶点的数量）或者所有边都已被考虑。

三、步骤

• 首先定义了一个Edge类，表示图中的边。它包含源节点(src)、目标节点(dest)和权重(weight)三个属性，并实现了Comparable接口，以便对边进行排序。
• 然后定义了一个KruskalMST类，其中包含了主函数main。在主函数中，首先定义了顶点数目V为4，然后创建了一个包含5条边的数组edges。每条边由源节点、目标节点和权重组成。
• 接下来，使用Arrays.sort()方法对边数组进行排序，按照权重从小到大的顺序排列。
• 创建一个UnionFind对象，用于实现并查集数据结构。并查集是一种用于处理不相交集合的数据结构，可以高效地合并和查找集合。
• 初始化一个变量mstWeight，用于计算最小生成树的总权重。
• 遍历排序后的边数组，对于每条边，通过并查集判断两个顶点是否属于同一棵树。如果不属于同一棵树，则将这条边添加到最小生成树中，并更新总权重。同时输出包含该边的相关信息。
• 最后输出最小生成树的总权重。
• UnionFind类是并查集的实现，包括了查找操作和联合操作。查找操作使用了路径压缩技术，以提高后续查找的效率。联合操作根据树的排名进行合并，以保持树的高度尽可能小。

四、算法实现

package com.lwtstu5.practice;
import java.util.Arrays;
 
class Edge implements Comparable<Edge> {
    int src, dest, weight;
 
    // Edge类的构造函数
    public Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }
 
    // 按照权重对Edge对象进行排序
    public int compareTo(Edge compareEdge) {
        return this.weight - compareEdge.weight;
    }
}
 
class KruskalMST {
    // 主函数
    public static void main(String[] args) {
        int V = 4; // 顶点数目
        Edge[] edges = new Edge[] {
                new Edge(0, 1, 10),
                new Edge(0, 2, 6),
                new Edge(0, 3, 5),
                new Edge(1, 3, 15),
                new Edge(2, 3, 4)
        };
 
        int E = edges.length;
        Arrays.sort(edges); // 按权重对边进行排序
 
        UnionFind unionFind = new UnionFind(V);
        long mstWeight = 0; // 用于计算MST的总权重
 
        // 遍历所有边，按照权重从小到大添加到MST
        for (Edge edge : edges) {
            int x = unionFind.find(edge.src);
            int y = unionFind.find(edge.dest);
 
            // 如果边的两个顶点不属于同一树（即它们的根不同），可以添加到MST中
            if (x != y) {
                unionFind.union(x, y);
                mstWeight += edge.weight; // 更新MST的总权重
                System.out.println("包含边 " + edge.src + "-" + edge.dest + " 权重: " + edge.weight);
            }
        }
 
        System.out.println("MST的总权重是: " + mstWeight);
    }
 
    // 并查集的实现
    static class UnionFind {
        private int[] parent;
        private int[] rank;
 
        public UnionFind(int V) {
            parent = new int[V];
            rank = new int[V];
            for (int i = 0; i < V; i++) {
                parent[i] = i;
                rank[i] = 0;
            }
        }
 
        // 查找操作，带路径压缩
        public int find(int i) {
            if (parent[i] != i) {
                parent[i] = find(parent[i]); // 路径压缩
            }
            return parent[i];
        }
 
        // 联合操作
        public void union(int x, int y) {
            int xRoot = find(x);
            int yRoot = find(y);
 
            // 根据排名进行合并
            if (rank[xRoot] > rank[yRoot]) {
                parent[yRoot] = xRoot;
            } else if (rank[xRoot] < rank[yRoot]) {
                parent[xRoot] = yRoot;
            } else {
                parent[yRoot] = xRoot;
                rank[xRoot] += 1;
            }
        }
    }
 
 
}

五、结果与分析