4. Kruskal Algorithm (크루스칼 알고리즘) : MST 찾기

public class Kruskal {
    static class Edge {
        int u, v;
        double weight;
        Edge(int u, int v, double weight) {
            this.u = u;
            this.v = v;
            this.weight = weight;
        }
    }
    static void findMST(int n, List<Edge> edges, List<Edge> MSTEdges) {
    	//Step 1. 간선들을 가중치에 따라 오름차 순으로 정렬
        Collections.sort(edges, (a, b) -> a.weight < b.weight ? -1 : 1); 
        
        //Step 2. disjoint set 선언 + rank배열은 0으로, 부모 배열을 자기 자신으로 초기화
        	//rank 배열은 랭크값이 작은 트리를 랭크값이 큰 트리에 포함시켜, 큰집합에 작은집합이 포함될 수 있도록 도와주는 역할.
        int[] parent = new int[n];
        int[] rank = new int[n];
        for(int i = 0; i < n; i++) parent[i] = i;
        int i = 0;
        
        //Step 3. n-1개의 간선들이 선택되어 MSTEdges 리스트이 담길 때까지 반복
        	//해당 간선에 연결된 노드 u, v의 부모를 찾는다.
        	//부모가 같은지 확인해주고(즉, 같은 집합에 속해있는지 아닌지) 부모가 다르다면 해당 간선을 MST에 추가시킨 뒤 두 집합을 합쳐준다.
        while (MSTEdges.size() != n-1 && i < edges.size()) {
        	Edge edge = edges.get(i++);
            int u = findParent(edge.u, parent);
            int v = findParent(edge.v, parent);
             
            if(u != v) {
            	MSTEdges.add(edge);
                union(u, v, parent, rank);
            }
        }
    }
    static int findParent(int u, int p[]) {
    	//최상위 부모를 찾아주는 함수. 루트에 해당하는 노드는 그 부모로 자기자신을 가지고 있기 때문에 재귀적으로 부모를 찾아준다.
        while(p[u] != u) u = p[u];
        return u;
    }
    static void union(int u, int v, int p[], int r[]) { 
    	//두개의 집합을 합쳐주는 함수. 랭크를 비교하여 랭크값이 더 큰 부분트리에 작은 부분트리가 연결될 수 있도록 해준다.
    	//만약 랭크값이 같다면, 둘중에 하나를 부모로 만들어주고 부모가 된 노드의 랭크값을 증가시킨다.
        if(r[u] > r[v]) p[v] = u;
        else if (r[u] < r[v]) p[u] = v;
        else {
            p[v] = u;
            r[u]++;
        }
    }
}