최소 스패닝 트리 - Prim(프림), Kruskal(크루스칼) 알고리즘 + Union-Find 자료구조

최소 스패닝 트리

Prim(프림), Kruskal(크루스칼) 알고리즘

+ Union-Find 자료구조

* 개요

- 신장 트리(스패닝 트리, Spanning Tree)란?

1. 그래프의 모든 정점이 간선으로 연결되어 있다.

2. 그래프 안에 사이클이 포함되어 있지 않다.

- 최소 신장 트리(최소 스패닝 트리, Minimum Spanning Tree)란?

말그대로 최소 비용으로 만들어진 신장 트리. 가중치의 합이 가장 작은 신장 트리

- 프림과 크루스칼 알고리즘은 최소 스패닝 트리를 구하는 방법 중 하나이다.

- 둘 다 Greedy Method을 기초로 하고 있다. (당장 눈앞의 최소 비용의 선택을 해서 결과적으로 최적의 Solution을 찾는다.)

- 프림은 정점 위주의 알고리즘, 크루스칼은 간선 위주의 알고리즘이다.

- 프림은 시작점을 정하고, 시작점에서 가까운 정점을 선택하면서 MST를 구성하므로 그 과정에서 사이클을 이루지 않지만

- 크루스칼은 시작점을 정하지 않고, 최소 비용의 간선을 차례로 대입하면서 MST를 구성하므로, 그 과정에서 사이클을 이루는지 항상 확인해야 한다. 사이클을 확인하는 방법으로는 Union-Find(Disjoint-Set) 방법이 있다.

- 시간 복잡도는 비슷하지만, 일반적으로 Dense한 그래프의 경우 프림이, 그렇지 않은 경우에는 크루스칼이 유리하다.

- 프림의 경우 최소 거리의 정점을 찾는 부분에서 자료구조의 성능에 영향을 받는다.

- 크루스칼은 간선을 weight 기준으로 정렬하는 과정이 오래 걸린다.

- 프림 : O(V^2+E) → O(E logV)

- 크루스칼 : O(E logE)

---

1. Prim's Algorithm (프림)

https://ko.wikipedia.org/wiki/%ED%94%84%EB%A6%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

---

2. Kruskal Algorithm (크루스칼)

https://ko.wikipedia.org/wiki/%ED%94%84%EB%A6%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

크루스칼 알고리즘은 아래 링크에서도 설명이 잘 되어 있습니다.

http://navercast.naver.com/contents.nhn?rid=2871&contents_id=86840

---

+ Union-Find 자료구조

( = Disjoint - Set 자료구조)

위 개요에서 크루스칼 알고리즘의 경우,

간선을 추가할 때마다 트리가 사이클을 이루는지 판단해야 한다고 했습니다.

이 때 활용할 수 있는 자료구조가 바로 Union-Find 자료 구조입니다.

이름에서 볼 수 있는 것처럼, Union 연산과 Find 연산이 가능합니다.

아래와 같은 그래프가 있다고 생각해봅시다.

현재 정점 0, 1, 2, 3이 연결되어 있고, 정점 4, 5, 6이 서로 연결되어 있습니다.

위 그래프를 아래와 같이 표현해 봅시다. 이렇게 표현하면

정점 0, 1, 2, 3은 정점 0의 그룹, 

정점 4, 5, 6은 정점 4의 그룹이라는 것을 쉽게 알 수 있습니다.

1) root 배열

int[] root = new int[7]; 배열을 선언합시다. 

root 배열의 값은 각 정점의 root를 나타냅니다. 그리고 각 그룹의 리더는 음수값을 갖습니다. (초기값이 -1이고 그룹이 커질수록 더 작아짐)

root[0] = -4

root[1] = 0, root[2] = 0, root[3] = 0

root[4] = -3

root[5] = 4, root[6] = 4

즉, 두 정점이 같은 그룹인지 확인하려면 각각의 정점의 root 노드를 구한 뒤 비교하면 되겠죠?

2) find 연산

위와 같이 각 정점의 root 노드를 알아내는 연산이 바로 find연산입니다.

    public int find(int a) {

        if (root[a] < 0) {

            return a;

        }

        return root[a] = find(root[a]);

    }

- a 정점의 root배열 값이 음수라면, 즉 자기가 root 노드이므로 a 자신을 리턴합니다.

- a 정점의 root배열 값이 음수가 아니라면, 재귀적 함수 호출로 root 노드를 찾습니다. 그리고 root[a]의 값을 갱신함으로써, 깊은 depth의 여러 정점들을 모두 root 노드 한단계 아래에 두게 됩니다.

예) 3번 정점과 5번 정점이 같은 그룹인가?

if ( find(3) == find(5) ) {

  

  // 같은 그룹이다.

}

else {

  // 다른 그룹이다.

}

3. Union 연산

이제 a정점과 b정점을 결합해 봅시다. 

1) a정점의 root 노드와 b정점의 root 노드를 구하고, 각각을 root1, root2라고 합시다.

  (두 값이 같으면 같은 노드이므로 그냥 return 해줍니다.)

2) 다른 노드인 경우, root1 노드의 그룹과 root2 노드의 그룹을 결합 해봅시다.

3) 큰 그룹에 작은 그룹을 결합할 것입니다. 따라서 어느 그룹의 size가 큰지 비교해야 합니다. ( 3줄짜리 XOR 연산은 swap 연산입니다.)

4) root1과 root2를 결합하고, root2의 부모를 root1로 설정합니다.

public void union(int a, int b) {

        int root1 = find(a);

        int root2 = find(b);

        // 이미 같은 그룹이라면

        if (root1 == root2) {

            return;

        }

        // 다른 그룹이라면

        // root1의 그룹이 더 작다면 (root1 &lt; root2)

        if (root[root1] &gt; root[root2]) {

            root1 ^= root2;

            root2 ^= root1;

            root1 ^= root2;

        }

        // root1과 root2를 결합하고, root2의 부모를 roo1로 설정

        root[root1] += root[root2];

        root[root2] = root1;

    }

* 전체 코드

class UnionFind {

    int[] root;

    public UnionFind(int V) {

        root = new int[V + 1];

        initialize();

    }

    public int find(int a) {

        if (root[a] &lt; 0) {

            return a;

        }

        return root[a] = find(root[a]);

    }

    public void union(int a, int b) {

        int root1 = find(a);

        int root2 = find(b);

        // 이미 같은 그룹이라면

        if (root1 == root2) {

            return;

        }

        // 다른 그룹이라면

        // root1의 그룹이 더 작다면 (root1 &lt; root2)

        if (root[root1] &gt; root[root2]) {

            root1 ^= root2;

            root2 ^= root1;

            root1 ^= root2;

        }

        // root1과 root2를 결합하고, root2의 부모를 roo1로 설정

        root[root1] += root[root2];

        root[root2] = root1;

    }

    private void initialize() {

        for (int i = 0; i &lt; root.length; i++) {

            root[i] = -1;

        }

    }

    // a를 포함하는 그룹의 정점의 개수를 확인하는 함수

    public int size(int a) {

        return -root[find(a)];

    }

}

---

* 대표 문제

http://stack07142.tistory.com/53