크루스칼 알고리즘 (Kruskal Algorithm), MST 최소 신장 트리

< 핵심 >

 

오름차순으로 정렬된 엣지를 하나씩 뽑아 노드에 연결되는 엣지로 사용할 것인지를 정하는 것이다.

 

 

 

< 구현 방식 >

 

즉, 두 노드의 루트가 다를 때 작은 값을 가지는 노드를 기준으로 루트를 union한다.

 

두 노드의 루트가 같다는 것은 하나로 연결이 되어 있다는 뜻이다.

 

(여기서 한 노드의 루트를 찾는 find 메서드(또는 함수)가 필요해진다.)

 

만약 두 노드의 루트가 같다면, 연결하지 않는다. → 싸이클(Cycle)이 생성될 수 있다.

 

예시 코드 (백준 BOJ 1922 네트워크 연결)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class edge implements Comparable<edge> {
    int a, b;
    int cost;

    edge(int a, int b, int cost){
        this.a = a;
        this.b = b;
        this.cost = cost;
    }

    @Override
    public int compareTo(edge e){
        return this.cost > e.cost ? 1 : -1;
    }
}

public class Main {
    static int[] p; // parent

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int V = Integer.parseInt(br.readLine());
        int E = Integer.parseInt(br.readLine());

        p = new int[V+1];
        for(int i=0; i<=V; ++i){
            p[i] = i;
        }

        StringTokenizer st;
        PriorityQueue<edge> pq = new PriorityQueue<>();
        for(int i=0; i<E; ++i){
            st = new StringTokenizer(br.readLine());
            pq.add(new edge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        // pq에 넣는 것은 오름차순으로 정렬하기 위한 것이다.
        for(edge e : pq){
            System.out.println(e.cost);
        }

        int ans = 0;

        // edge 수만큼 반복
        for(int i=0; i<E; ++i){
            edge e = pq.poll();

            // 원래 e의 null 검사를 해줘야 한다.
            int aRoot = find(e.a);
            int bRoot = find(e.b);

            // 여기서 이미 비교를 했으므로 union 에서 할 필요가 없다;
            if(aRoot != bRoot){
                union(aRoot, bRoot);
                ans += e.cost;
            }
            // 같으면 무시 --> 싸이클 생성 방지
        }
        System.out.print(ans);
    }

    // 루트 찾아서 반환
    public static int find(int a){
        if(a != p[a]){
            p[a] = find(p[a]);
            return p[a];
        }
        return a;
    }

    // 루트 일치화
    public static void union(int aRoot, int bRoot){
        // + 이미 루트를 구했으므로 구할 필요가 없다.
        // + 이미 main 반복문에서 비교했으므로 할 필요가 없다.

        // a가 더 작은 수니까 a를 넣는 게 맞다.
        p[bRoot] = aRoot;
    }
}

 

< 활용 >

 

모든 노드를 최소의 비용으로 연결시키는 설계에 유용하다.

 

( 각 노드는 한 번씩만 연결되며 싸이클은 존재하지 않는다. )

 

 

 

< 참고 >

 

실제로 그래프가 만들어진 것은 아니지만,

 

union을 할 때 노드를 연결하는 로직을 주입하면 연결 정보를 사용할 수 있게 된다.