[Algorithm] 최소신장트리(MST) - Kruskal

[Algorithm] 최소신장트리(MST) - Kruskal

간선을 하나씩 선택해서 MST를 찾는 알고리즘

1. 최소, 모든 간선을 가중치에 따라 오름차순으로 정렬
2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴
   • 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택
3. n-1개의 간선이 선택될 때 까지 2를 반복

code

Edge

public class Edge {
    int adjvertex; // 간선의 다른쪽 끝 정점
    int weight;    // 간선의 가중치
    public Edge(int v, int wt) {
        adjvertex = v;
        weight    = wt;
    }
}

KruskalMST

import java.util.*;
public class KruskalMST {
    int N, M; // 그래프 정점, 간선의 수
    List<Edge>[] graph;
    UnionFind uf; // Union-Find 연산을 사용하기 위해    
    Edge[] tree;    
    static class Weight_Comparison implements Comparator<Edge> { //weight를 기준으로 우선순위큐를  사용하기 위해
        public int compare(Edge e, Edge f) {
            if(e.weight > f.weight)
                return 1;
            else if(e.weight < f.weight)
                return -1;        
            return 0;
        }        
    }
    public KruskalMST(List<Edge>[] adjList, int numOfEdges) {
        N = adjList.length;
        M = numOfEdges;
        graph = adjList;
        uf = new UnionFind(N);    // Union-Find 연산을 사용하기 위해    
        tree = new Edge[N-1];
    }
    public Edge[] mst()    {  // Kruskal 알고리즘        
        Weight_Comparison BY_WEIGHT = new Weight_Comparison();  // 우선순위큐를  weight 기준으로 구성하기 위해        
        PriorityQueue<Edge> pq = new PriorityQueue<Edge>(M, BY_WEIGHT);  // 자바 라이브러리의 우선순위큐 사용
                                    // 우선순위큐의 크기로 M(간선의 수)을 지정, BY_WEIGHT는 line 24의 comparator
        for (int i = 0; i < N; i++){ 
            for (Edge e : graph[i]){
                pq.add(e);  // edgeArray의 간선 객체들을 pq에 삽입
            }
        }        
        int count = 0;    
        while (!pq.isEmpty() && count < N-1) {
            Edge e = pq.poll();          // 최소 가중치를 가진 간선를 pq에서 제거하고 가져옴
            int u = e.vertex;            // 가져온 간선의 한 쪽 정점
            int v = e.adjvertex;          // 가져온 간선의 다른 한 쪽 정점
            if (!uf.isConnected(u, v)) { // v와 w가 각각 다른 집합에 속해 있으면
                uf.union(u, v);          // v가 속한 집합과 u가 속한 집합의 합집합 수행
                tree[count++] = e;       // e를 MST의 간선으로서 tree에 추가
            }
        }            
        return tree;
    }
}

UnionFind

public class UnionFind {  
    protected  int[] p;    // 배열크기는 정점의 수 N이고 p[i]는 i의 부모 원소를 저장한다. 
    protected  int[] rank; 

    public UnionFind(int N) {
        p = new int[N];
        rank = new int[N];
        for (int i = 0; i < N; i++) {
            p[i]    = i;  // 초기엔 N개의 트리가 각각 i 자기 자신이 부모이기 떄문에 
            rank[i] = 0;  // 초기엔 N개의 트리 각각의 rank를 0으로 초기화 
        }
    }
    //i가 속한 집합의 루트노드를 재귀적으로 찾고 최종적으로 경로상의 각 원소의 부모를 루트노드로 만든다.
    protected int find(int i) { // 경로 압축
        if ( i != p[i])   
            p[i] = find(p[i]);  //리턴하며 경로상의 각 노드의 부모가 루트가되도록 만든다.
        return p[i];
    }
    //i와 j가 같은 트리에 있는지를 검사
    public boolean isConnected(int i, int j) {
        return find(i) == find(j); 
    }
    public void union(int i, int j) {  // Union 연산
        int iroot = find(i);
        int jroot = find(j);
        if (iroot == jroot) return;  // 루트노드가 동일하면 더이상의 수행없이 그대로 리턴
        // rank가 높은 루트노드가 승자로 union을 수행한다.
        if (rank[iroot] > rank[jroot]) 
            p[jroot] = iroot;               // iroot가 승자
        else if (rank[iroot] < rank[jroot]) 
            p[iroot] = jroot;               // jroot가 승자
        else {
            p[jroot] = iroot;  // 둘중에 하나 임의로 승자
            rank[iroot]++;     // iroot의 rank 1 증가
        }
    }
}

수행시간

간선을 정렬(또는 우선순위큐의 삽입과 삭제)하는데 소요되는 시간 $O(MlogM) = O(MlogN)$

신장트리가 만들어질 때까지 간선에 대해 isConnected()와 union()을 수행하는 시간 $O((M+N)logN)$
$$
O(MlogN) + O((M+N)logN) = O(MlogN)
$$

Reference

『IT CookBook, 자바로 배우는 쉬운 자료구조』, 이지영 집필, 한빛아카데미(2008)

『SW 문제해결 응용 - 구현 - 그래프의 최소 비용 문제』
https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AV3GBeD6AF4BBARB#