Kruskal's algorithm : 최소 신장 트리(MST, Minimum Spanning Tree) 찾기

BOJ 문제 최소 스패닝 트리(1197), 도시 분할 계획(1647), 네트워크 연결(1922) 등의 문제들을 풀기 위해 Kruskal Algorithm을 공부했다.

1. 알고리즘

최소 신장 트리(MST, Minimum Spanning Tree)는 가중치(weight)가 있는 간선(edge)들을 갖고 있는 그래프에서, 그래프의 모든 정점(vertex)들을 포함한 트리(tree)이면서, 그 트리가 가진 모든 간선의 가중치의 합이 가장 작게 되는 그래프를 말한다. 예를 들면, 아래의 그래프 G에서 모든 정점을 포함한 트리는 가운데의 그래프에서 빨간 간선들로 이루어진 그래프이고, 그러한 트리는 여러 개가 있을 수 있다.(모든 정점을 포함한 트리를 spanning tree라고 한다.) 하지만, 간선의 가중치의 합이 가장 작게 되는 그래프는 가장 오른쪽에 있는 트리이고, 그것이 최소 신장 트리가 된다.

그림 1

Kruskal's algorithm은 최소 신장 트리를 찾는 알고리즘이다. 그래프의 정보, 즉, V개의 정점, E개의 간선과 각각의 가중치들이 주어진 상황에서 Kruskal Algorithm은 다음과 같이 작동한다.

1. 가중치가 작은 간선부터 하나씩 선택하여 그래프를 구성한다. 이 때, 추가되는 간선이 순환 그래프(cycle)를 만든다면 추가하지 않는다.
2. 간선의 개수가 V - 1개가 되면, 추가적으로 간선을 선택하지 않는다.

Note. 정점이 V개, 간선이 V - 1개이고, 순환 그래프를 포함하지 않는 그래프는 트리다.(V는 무한대가 아님.)

 

[그림 1]의 예제로 작동을 확인해보자. 그래프 G는 7개의 정점, 11개의 간선이 주어져있다. 가중치가 가장 작은 간선은 가중치가 1인 2개의 간선인데, 두 간선을 선택해도 순환 그래프가 만들어지지 않으므로 2개의 간선을 모두 선택할 수 있다.([그림 2], 왼쪽) 그 다음으로 가중치가 작은 간선은 가중치가 2인 2개의 간선인데, 이전과 마찬가지로 두 간선을 선택해도 순환 그래프가 만들어지지 않으므로 2개의 간선을 모두 선택할 수 있다.([그림 2], 오른쪽)

그림 2

다음으로, 가중치가 3인 간선을 선택하게 되면 순환 그래프가 만들어지므로 선택할 수 없고, 가중치가 4인 간선을 선택해야 한다.([그림 3], 왼쪽) 마지막으로, 가중치가 5, 6, 7인 간선을 선택하면 순환 그래프가 만들어지므로 선택할 수 없고, 가중치가 8인 간선을 선택해야한다.([그림 3], 오른쪽)

그림 3

참고로, 정점에 인덱스를 부여하는 것으로 선택하는 간선의 순서를 정해줄 수 있다.(예제에서 가중치가 1, 2인 간선들을 선택할 때에도 알고리즘의 규칙이 잘 정의될 수 있다.)

 

하지만, 알고리즘의 작동을 확인하는 것으로는, 이 알고리즘으로 찾은 트리의 가중치의 합이 최소가 된다는 것을 확인할 수는 없다. 모든 신장 트리(spanning tree)와 비교했다는 보장은 없기 때문이다. 아래는 임의의 최소 신장 트리가 Kruskal algorithm으로 찾은 트리와 가중치의 합이 같음을 증명한 것이다.

그림 4. 알고리즘의 유효성 증명

2. 코드(Java)

지금부터 설명할 코드는 BOJ 문제 최소 스패닝 트리(1197)의 답안이다. 비슷한 유형의 문제도 이 코드를 조금씩 수정해서 해결할 수 있었다.

 

입력으로 정점의 개수 V, 간선의 개수 E가 주어지고, E개의 간선의 정보들이 주어진다고 하자. [그림 1]의 예제는 다음과 같은 입력이 들어왔을 때 볼 수 있는 그래프라고 할 수 있다. (간선에는 방향이 없다.)

7 11
1 2 2 // 정점1 정점2 가중치
2 3 1
3 4 8
3 5 3
5 6 4
6 7 1
6 1 5
1 5 2
3 6 6
5 2 7
6 7 1

나는 가중치가 작은 간선부터 선택하는 것을 구현하기 위해, 간선의 정보를 담는 Edge 클래스를 만들고, 가중치로 대소 관계를 구분하도록 설정했다. 그러면 우선순위 큐를 이용해서 입력되는 간선들을 저장해서 사용할 수 있다. 다음은 Edge 클래스의 코드이다. 

class Edge implements Comparable<Edge> {
    int v1, v2;
    int weight;
    public Edge(int v1, int v2, int weight) {
        this.v1 = Math.min(v1, v2);
        this.v2 = Math.max(v1, v2);
        this.weight = weight;
    }
    @Override
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}

Memo. equals() 메서드를 만들어야 할 지 잠깐 고민했었다. 만드는 습관을 들이면 좋을 것 같은데, 아직 익숙하지 않아서 연습이 필요할 것 같다. 

 

그리고 순환 그래프(cycle)를 만드는 것을 피하기 위해 union-find 자료구조를 사용한다. 그래프를 구성할 때, 간선으로 연결된 두 정점이 같은 집합에 있는지 확인하고(같은 집합에 있다면 순환 그래프를 만들게 되므로), 같은 집합에 없다면 두 정점을 하나의 집합으로 합친다. 이 과정을 선택되는 간선의 개수가 V - 1개가 될 때까지 반복한다. 다음은 이것을 구현한 전체 코드이다.

import java.io.IOException;
import java.util.PriorityQueue;

public class Main {
    static int V, E, count = 0;
    static int[] parentRecord;
    static PriorityQueue<Edge> edges;
    static long weightSum = 0;
    public static void main(String[] args) throws IOException {
        setVariables();
        while (count < V - 1) {
            Edge tmp = edges.poll();
            if (union(tmp.v1, tmp.v2)) {
                count++;
                weightSum += tmp.weight;
            }
        }
        System.out.println(weightSum);
    }
    public static int readInt() throws IOException {
        int val = 0;
        int c = System.in.read();
        while (c <= ' ') {
            c = System.in.read();
        }
        boolean flag = (c == '-');
        if (flag)
            c = System.in.read();
        do {
            val = 10 * val + c - 48;
        } while ((c = System.in.read()) >= 48 && c <= 57);

        if (flag)
            return -val;
        return val;
    }
    public static void setVariables() throws IOException {
        V = readInt();
        E = readInt();
        parentRecord = new int[V + 1];
        for (int i = 1; i < V + 1; i++) {
            parentRecord[i] = i;
        }
        edges = new PriorityQueue<>();
        for (int i = 0; i < E; i++) {
            int A = readInt(), B = readInt(), C = readInt();
            edges.add(new Edge(A, B, C));
        }
    }
    public static int find(int x) {
        if (parentRecord[x] == x) return x;
        return find(parentRecord[x]);
    }
    public static boolean union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (x < y) parentRecord[y] = x;
        else parentRecord[x] = y;
        return true;
    }
}

문제 최소 스패닝 트리(1197) 에서는 최소 신장 트리의 가중치의 합을 구하는 문제여서 weightSum 변수에 가중치를 더해주는 것으로 구현했는데, 간선의 정보들을 기록하도록 구현할 수도 있다.

Memo. union-find 자료구조를 사용하는 부분에서, union() 메서드와 find() 메서드를 최적화하는 방법이 있다는 것을 알게 되었는데, 이 코드에는 적용되어 있지 않다. union-find 자료구조에 대해서 조금 더 공부해서, 최적화 방법에 대해서도 정리해보자.

---

최소 신장 트리를 찾는 알고리즘은 Kruskal's algorithm 말고도 Prim's algorithm이 있다고 한다. 다음에는 그 알고리즘에 대해서도 공부해보고 비교해봐도 좋을 것 같다.