[알고리즘] 최소비용 신장트리(MST) - Kruskal 알고리즘

1. 최소비용 신장트리(MST, Minimum Spanning Tree)란?

---

먼저, 신장 트리(ST, Spanning Tree)는 사이클 없이 모든 노드를 연결하는 트리입니다.

1. 모든 정점을 포함한다.
2. 정점간 서로 연결되면서 사이클이 존재하지 않는 그래프이다. (트리의 조건이기도 하죠? 😉  틈새공부)

그래프에 여러 개의 신장 트리가 존재할 수 있는데, 이 중 간선의 가중치 합이 최소인 것을 최소비용 신장트리(MST)라 합니다.

2. Kruskal 알고리즘이란?

---

Kruskal 알고리즘은 최소비용 신장트리(이하 MST)를 찾는 대표적인 알고리즘입니다.
MST를 구하는 알고리즘으로 Prim 알고리즘도 있는데, Prim은 정점을 기준으로 한다면, Kruskal은 간선을 기준으로 합니다. 
아래와 같은 그래프에서 MST를 찾아보겠습니다.

[그림 1] 그래프 예시

가장 적은 비용으로 연결만 시키면 되기 때문에 간선의 가중치를 기준으로 가중치가 적은 것부터 하나씩 그래프에 포함시켜나가면 됩니다.

먼저, 위 그래프에서 간선을 오름차순으로 정렬하면 다음과 같습니다.

[그림 2] 위 그래프에서 간선의 가중치를 기준으로 오름차순 정렬

그럼 위 테이블을 참고해 가중치가 적은 간선부터 하나씩 그래프에 추가해보겠습니다.

[그림 2] 간선의 가중치가 낮은 순으로 하나씩 추가해나간다.

그래프에서 간선을 하나씩 추가해나가다가 사이클이 형성되는 (1, 3) 간선을 만나면 그리지않고 넘어갑니다.
자, 그럼 간선을 추가했을 때 사이클이 형성되는지는 어떻게 알 수 있을까요? 🤔
바로 이때 사용되는게 Disjoint-Set 자료구조입니다. (참고 --> Disjoint-Set이란?)

최종적인 MST는 다음과 같습니다.

[그림 3] 최종적인 MST의 모습

3. 코드

---

Kruskal 알고리즘은 Disjoint-Set 자료구조를 기반으로 하기 때문에 선행이 되어 있어야 합니다. (위 링크를 참조해주세요. 🙂 )

public class Main {
    public static int[] parent;
    public static PriorityQueue<Edge> pq = new PriorityQueue<>();
    
    public static void main(String[] args) {
        // 간선을 PriorityQueue에 담습니다. (가중치를 기준으로 정렬됩니다.)
        pq.offer(new Edge(3, 6, 2));
        pq.offer(new Edge(2, 3, 3));
        pq.offer(new Edge(1, 2, 4));
        pq.offer(new Edge(3, 5, 5));
        pq.offer(new Edge(3, 4, 6));
        pq.offer(new Edge(1, 3, 7));
        pq.offer(new Edge(5, 6, 8));
        pq.offer(new Edge(2, 4, 9));
        pq.offer(new Edge(4, 6, 12));
        
        // Disjoint-Set의 Make_Set 연산에 해당합니다.
        parent = new int[7];
        for (int i = 1; i <= 6; i++) {
            parent[i] = i;
        }
            
        int sum = 0, size = 0;
        while (!pq.isEmpty()) {
            if (size == 6 - 1) break; // MST의 간선갯수는 (정점의 수-1)입니다.
            Edge edge = pq.poll();
            
            // 두 정점이 같은 그래프에 속하는지 Disjoint-Set의 Find 연산으로 확인합니다.
            if (find(edge.u) != find(edge.v)) {
                union(edge.u, edge.v) // 두 정점을 하나의 그래프로 합칩니다. Disjoint-Set의 Union 연산
                sum += edge.weight;
                size++;
            }
        }
        System.out.println("총 비용: " + sum);
    }
    
    public static void union(int x, int y) {
        x = find(x);
        y = find(y);
        parent[y] = x;
    }
    
    public static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }
}
class Edge implements Comparable<Edge> {
    int u, v, weight;
    
    Edge(int u, int v, int weight) {
        this.u = u;
        this.v = v;
        this.weight = weight;
    }
    
    @Override
    public int compareTo(Edge o) {
        return weight - o.weight;
    }
}

4. 참고자료

---

[1] https://namu.wiki/최소비용 신장트리

[2] https://blog.naver.com/ndb796/221230994142

[3] https://brenden.tistory.com/36?category=747314