Kruskal 크루스칼 알고리즘

package Z_Project;
 
import java.util.Arrays;
import java.util.Scanner;
 
/**
 * MST 알고리즘 중 KRUSKAL이 더 직관적이고 간단(많이 사용됨) DisjointSets
 */
 
/*
 * 
input

6 11
5 3 18
1 2 21
2 6 25
0 2 31
0 1 32
3 4 34
5 4 40
2 4 46
0 6 51
4 6 51
0 5 60


output

5-3 18
1-2 21
2-6 25
0-2 31
3-4 34
2-4 46

 * 
 * */
public class Z37_KRUSKAL {
    public static int[] p; //부모를 저장할 배열
    public static int[] rank;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();
        int E = sc.nextInt();
        p = new int[V+1];
        rank = new int[V+1];
        
        Edge[] ed = new Edge[E];
        
        for(int i=0;i<E;i++) {
            ed[i] = new Edge(sc.nextInt(),sc.nextInt(),sc.nextInt());
        }
        Arrays.sort(ed); //정렬하기 위해서 compareTo()를 작성해야한다.
        
        for(int i=0;i<p.length;i++) {
            makeSet(i);
        }
        
        for(int i=0;i<ed.length;i++) { //가중치가 낮은 간선부터 선택하기
            Edge e = ed[i];
            if(findSet(e.a) != findSet(e.b)) { //서로 다른 집합일 경우만 합치기
                union(e.a,e.b);
                System.out.println(e.a+"-"+e.b+" "+e.val);
            }
        }
    }//end of main
    
    public static void printSet() {
        System.out.print("index : ");
        for(int i=0;i<p.length;i++) {
            System.out.printf("%2d ", i);
        }
        System.out.print("\nparent: ");
        for(int i=0;i<p.length;i++) {
            System.out.printf("%2d ", p[i]);
        }        
        
        System.out.println("\n");
    }
    
    
    /*멤버 x를 포함하는 새로운 집합을 생성*/
    public static void makeSet(int x) {
        p[x]=x; //부모 : 자신의 index로 표시 or -1
        //rank[x] = 0;//초기값 0임, 생략가능
    }
    
    /*멤버 x를 포함하는 집합의 대표자를 리턴*/
    public static int findSet(int x) {
        if(x==p[x]) return x;
        else {
            p[x]=findSet(p[x]); // Path Compression
            //rank[x]=1;//할 필요 없다. 대표자의 깊이(rank)만 알면된다.
            return p[x];
        }
    }
    
    public static void union(int x,int y) {
        int px = findSet(x);
        int py= findSet(y);
        
        // 서로 다른 집합일 경우만 합친다.
 
        if(px!=py) {
        //    p[py]=px; //대표자 합치기    
            link(px,py);
        }
    }
    
    /*x의 대표자의 집합과 y의 대표자의 집합을 합침, rank도 맞춤*/
    public static void link(int px, int py) {
        if(rank[px]>rank[py]) {
            p[py]=px; //작은쪽에 큰쪽을 붙인다.
        } else {
            p[px]=py;
            
            if(rank[px]==rank[py]) { //같은 경우는 rank 값이 증가
                rank[py]++;//집합의 대표자 랭크가 증가됨.
            }
        }
    }
    
    public static class Edge implements Comparable<Edge>{
        int a; //정점1
        int b; //정점2
        int val; //가중치
        public Edge(int a, int b, int val) {
            this.a = a;
            this.b = b;
            this.val = val;
        }
        @Override
        public int compareTo(Edge o) { //비교기준
            return this.val-o.val;
        }
        
        
    }
}