题目描述

Kruskal算法求最小生成树

JAVA 代码

/*
解题思路：
kruskal算法求最小生成树的思路是每一次选取权值最小的边，
如果选择的边所对应的两个顶点已经在一个连通块中，就不加这条边，
最后判断加边的数量等不等于顶点数减1，如果不等，说明这张图不能生成最小生成树。

时间复杂度分析：
kruskal算法的时间复杂度为O(m∗log2m)
*/

import java.util.*;
import java.io.*;

class Edge{
    int a,b,c;
    Edge(int a,int b, int c){
        this.a = a;
        this.b = b;
        this.c = c;
    }
}


class Main{
    static int N = 500010;
    static int[] p = new int[N];

    static int find (int x){
        if(x!= p[x]){
            p[x] = find(p[x]);
        }
        return p[x];
    }
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

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

        Edge[] g = new Edge[m];

        for(int i = 0;i<m;i++){
            g[i] = new Edge(sc.nextInt(),sc.nextInt(),sc.nextInt());
        }

        //kruskal算法求最小生成树的思路是每一次选取权值最小的边
        //所以 先排序
        Arrays.sort(g, new Comparator<Edge>(){

            @Override
            public int compare(Edge e1, Edge e2){
                return e1.c - e2.c;
            }
        });


        int cnt = 0, res =0;
        //循环两个点.是否在同一集合内. 
        for(int i=0;i<m;i++){
            Edge t = g[i];
            int a = t.a, b = t.b, c = t.c;
            a = find(a);
            b = find(b);
            //如果不在一个集合, 连一条边.
            if(a!=b){
                cnt++;
                res += c;
                p[a] = b;
            }
        }
        //如果加边次数 是点数-1. 则有最小生成树
        if(cnt == n-1)System.out.println(res);
        else System.out.println("impossible");
    }
}