Kruskal 算法最小生成树-Toy模板网

这篇具有很好参考价值的文章主要介绍了Kruskal 算法最小生成树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.按边从小到大进行排序
2.从小到大进行加边，保证加入的边的两端点不连通，即保证不形成回路文章来源地址https://www.toymoban.com/news/detail-690362.html

 BufferedReader  reader = new BufferedReader(new InputStreamReader(System.in)); //缓存字符输入流 先将输入放到缓存区中
 BufferedWriter writer= new BufferedWriter((new OutputStreamWriter(System.out))); //高速输出流
 n = Integer.parseInt(arr1[0]);// 将字符串数字转换成int

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;

public class Main {

    private  static int N = 100010;
    private  static int M = 200010;

    private static int n,m;

    private static int[] p = new int[N];

    private  static  int cnt;
    private  static  int res;

    private static class Node{
        private int a;
        private int b;
        private int c;

        public Node(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "a=" + a +
                    ", b=" + b +
                    ", c=" + c +
                    '}';
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader  reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer= new BufferedWriter((new OutputStreamWriter(System.out)));

        String[] arr1 = reader.readLine().split(" ");

        n = Integer.parseInt(arr1[0]);
        m = Integer.parseInt(arr1[1]);

        Node[] nodes = new Node[m];

//        int a,b,c;

        for(int i = 0; i < m; i++){
            String[] arr2 = reader.readLine().split(" ");
            int a = Integer.parseInt(arr2[0]);
            int b = Integer.parseInt(arr2[1]);
            int c = Integer.parseInt(arr2[2]);

            nodes[i] = new Node(a,b,c);

        }

        // 排序 sort重载 实现定制排序
        Arrays.sort(nodes, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.c - o2.c; //从小到大进行排序
            }
        });

        // 选择边
        //定义每个人的祖宗

        for(int i = 1; i <= n; i++){
            p[i] = i;
        }

        for(int i = 0; i < m; i++){
            int a = nodes[i].a;
            int b = nodes[i].b;
            int c = nodes[i].c;
            if(find(a) != find(b)){
//                System.out.println("f : "+ find(a) + " " + find(b));

                p[find(a)] = find(b);
//                System.out.println(a + " " + b);
                cnt++;
                res += c;
            }
        }

//        System.out.println(cnt + " " + res);
        if(cnt == n-1){
            System.out.println(res);
        }else System.out.println("impossible");

//        System.out.println(Arrays.toString(nodes));






    }

    public static int find(int a){
        if(p[a] != a){
            p[a] = find(p[a]);
        }

        return  p[a];
    }
}