【数据结构】图的最小生成树克鲁斯卡尔（Kruskal）算法

约定不等于承诺〃 2022-04-04 05:08 195阅读 0赞

### 说明 ###

1.  利用克鲁斯卡尔算法
2.  打印出各连通分类的边集
3.  要是连通图才能生成最小生成树

### 运行截图 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hbl96dW8_size_16_color_FFFFFF_t_70]

### 代码实现 ###

import java.util.*;
    
    public class MinSpanTreeTest {
        
    
    
        public static void main(String[] args) {
        
            MinSpanTree minSpanTree = new MinSpanTree();
            minSpanTree.CreatGraph();//创建图
            minSpanTree.Kruskal();//利用Kruskal算法生成最小生产树
        }
    }
    class Vertex{
         //顶点类
        String vername;//顶点的名称
    }
    class Edge{
         //弧
        int a,b;//弧的两个端点在顶点数组里的下标
        int weight;//权值
    }
    class MinSpanTree{
        
        private ArrayList<Vertex> vertices = new ArrayList<>();//顶点的集合
        private Edge[] edges;//弧的集合
        private int VerNum;//顶点的数量
        private int EdgeNum;//弧的数量
        public  int find(String vername){
        //根据顶点名称确定该顶点的位置
            for (int i=0;i<VerNum;i++){
        
                if (vertices.get(i).vername.equals(vername))
                    return i;
            }
            return  -1;//说明没有该顶点
        }
    
        public void CreatGraph(){
        //创建图
            Scanner in = new Scanner(System.in);
            System.out.println("输入顶点的数量");
            VerNum = in.nextInt();
            System.out.println("输入弧的数量");
            EdgeNum =in.nextInt();
            edges = new Edge[EdgeNum];//弧的集合，edges[0]不用
            System.out.println("输入各个顶点的名称");
            for (int i=0;i<VerNum;i++){
        //读取各个顶点名称，存入数组中
              Vertex  vertex = new Vertex();
                vertex.vername = in.next();
                vertices.add(vertex);
            }
            System.out.println("依次输入各条弧的两个顶点和权值");
            for (int i=0;i<EdgeNum;i++){
        
                String a = in.next();//读取弧的相关信息
                String b = in.next();
                int weight = in.nextInt();
                int aIndex=find(a);//根据顶点名字返回该顶点在顶点数组中的位置
                int bIndex=find(b);
                if (aIndex==-1||bIndex==-1){
         //位置为-1时输入的顶点名称在顶点数组找不到
                    System.out.println("顶点名称输入错误，请重新输入");
                    i--;
                    continue;
                }
                else{
         //顶点名称都输入正确
                    Edge edge = new Edge();//实例化一条弧
                    edge.a = aIndex;//弧的两个端点（顶点）a,b在顶点数组里的下标
                    edge.b = bIndex;
                    edge.weight =weight;//权值
                    edges[i] = edge;//放入弧集合中
                }
            }
            Arrays.sort(edges, new Comparator<Edge>() {
         //按照权值大小重新排列各条弧
                @Override
                public int compare(Edge o1, Edge o2) {
        
                    return o1.weight-o2.weight;
                }
            });
        }
        //一开始把图的每个顶点都当成一颗独立的树，通过不断组合，把这个森林变成来只有同一颗顶点的树
        int [] parent;//记录每个顶点所在子树的根结点的下标
        int [] child ;//记录每个顶点为根结点时，其所拥有的孩子节点的个数
        public int findRoot(int child){
        
            //找到该顶点的所在的树的根结点，初始的时候每个顶点都是一棵树的根结点
            if (parent[child]==child)  //自己就是根节点
                return child;
            parent[child] = findRoot(parent[child]);//递归查找
            return  parent[child];//返回找到根节点
        }
        boolean unionTree(Edge e){
        //合并两个子树
            //找到该条边所在树的根结点
            int root1;
            int root2;
            root1 = findRoot(e.a);
            root2 = findRoot(e.b);
            if (root1!=root2){
        //只有两个顶点不在同一颗子树上，才能把两颗树并成一颗
                //小树和并到大数，看他们的孩子的个数
                if (child[root1]>child[root2]){
        
                    parent[root2]=root1;//小树的顶点设置为大树的顶点
                    child[root1]+=child[root2]+1;//+1是 root2顶点也变成一个孩子节点
                }
                else{
        
                    parent[root1]=root2;
                    child[root2]+=child[root1]+1;
                }
                return true;
            }
            return false;
        }
        public void Kruskal(){
         //用克鲁斯卡尔算法生成最小生成树
            parent = new int[VerNum];
            child = new  int[VerNum];
            for (int i=0;i<VerNum;i++){
        
                parent[i]=i;//初始的时候每个顶点都是一棵树的根结点
                child[i]=0;//孩子数为0
            }
            int count=0;//加入的边的数量
            System.out.println("最小生成树的各边及其对应的权值为");
            for (int i=0;i<EdgeNum;i++){
        
                if (unionTree(edges[i])==true){
        //如果两棵树可以和合在一起说明是生成树的一条边
                    //根据端点的下标值在顶点数组里找到对应的顶点
                    Vertex vertex1 = vertices.get(edges[i].a);
                    Vertex vertex2 = vertices.get(edges[i].b);
                    System.out.println(vertex1.vername+"--"+vertex2.vername+"    "+edges[i].weight);
                    count++;
                }
                if (count==VerNum-1){
         //当加入的边的数量等于 顶点数-1 说明查找完成
                    break;
                }
            }
            if(count!=VerNum-1){
        
                System.out.println("该图为非连通图，无法构成最小生成树");
            }
        }
    
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hbl96dW8_size_16_color_FFFFFF_t_70]: /images/20220404/7edb62891a744468a49635d976f20575.png