티스토리 뷰

반응형

Table of Contents


개요

최소 스패닝 트리 ( minimum spanning tree )

크루스칼 알고리즘 ( Kruskal's algorithm )

크루스칼 알고리즘의 구현

크루스칼 알고리즘 코드

문제

크루스칼 알고리즘의 정당성




1. 개요


 크루스칼 알고리즘은 무향 연결 그래프가 주어질 때, '최소 스패닝 트리' 라고 부르는 서브 그래프를 찾는 알고리즘입니다. 크루스칼 알고리즘은 유니온 파인드 자료구조를 사용하므로, 해당 자료구조를 모른다면 유니온 파인드 설명을 보고 오시는 걸 추천합니다.




2. 최소 스패닝 트리 ( minimum spanning tree )


 스패닝 트리란, 해당 그래프의 모든 정점을 포함하는 트리 형태의 서브 그래프를 뜻합니다. 왼쪽의 그래프에서 스패닝 트리를 하나 찾아보면 오른쪽의 트리가 나옵니다.




 그래프에서 스패닝 트리는 여러 개가 있을 수 있습니다. 위의 예시에서도 다른 스패닝 트리를 찾아보면 금방 찾을 수 있지요. 그런 스패닝 트리들 중에서 간선의 가중치의 합이 가장 작은 스패닝 트리를 최소 스패닝 트리라고 부릅니다.

(위에서 예시로 든 스패닝 트리의 '간선의 가중치의 합' = 4+2+6+8+11 = 31 입니다.)


 물론, 최소 스패닝 트리도 여러 개 있을 수 있습니다. 크루스칼 알고리즘은 그런 최소 스패닝 트리 중 하나를 찾음으로서 간선의 가중치의 합의 최솟값을 찾는 알고리즘입니다. 참고로, 최소 스패닝 트리는 줄여서 MST 라고도 불립니다.




3. 크루스칼 알고리즘 ( Kruskal's algorithm )


 크루스칼 알고리즘은 아래와 같은 '그리디'스러운 알고리즘입니다. 이 알고리즘을 따라가면 최소 스패닝 트리를 구할 수 있습니다.


step 0) 모든 간선을 끊어 놓는다.

step 1) 가중치 순으로 간선들을 정렬한다. (오름차순)

step 2) 정렬된 간선을 순서대로 선택한다.

step 3) 선택한 간선의 두 정점이 연결되어 있지 않으면, 해당 간선을 최소 스패닝 트리에 포함 시키고 두 정점을 연결한다.

              ( 1-2-3 처럼 간접적인 연결이어도 1,3 은 연결되어 있는 걸로 친다.)


 예시 그래프를 통해 알고리즘을 따라가 보겠습니다. 편의 상, 연결되지 않은 간선은 점선, 연결된 간선은 실선으로 표현하겠습니다.




step 0) 모든 간선을 끊어 놓는다.


step 1) 가중치 순으로 간선들을 정렬한다. (오름차순)


 위는 연결된 정점들, 아래는 가중치로 표현하면 아래와 같이 정렬됩니다.


step 2) 정렬된 간선을 순서대로 선택한다. ->  정점 = 2, 3, 가중치 = 2


step 3) 2, 3은 연결되어 있지 않으므로, 선택된 간선을 통해 연결한다. ->  정점 = 2, 3, 가중치 = 2



step 2) 정렬된 간선을 순서대로 선택한다. ->  정점 = 4, 5, 가중치 = 3


step 3) 4, 5은 연결되어 있지 않으므로, 선택된 간선을 통해 연결한다. ->  정점 = 4, 5, 가중치 = 3




step 2) 정렬된 간선을 순서대로 선택한다. ->  정점 = 1, 3, 가중치 = 4


step 3) 1, 3은 연결되어 있지 않으므로, 선택된 간선을 통해 연결한다.->  정점 = 1, 3, 가중치 = 4



step 2) 정렬된 간선을 순서대로 선택한다.  ->  정점 = 1, 2, 가중치 = 5


step 3) 1, 2은 연결되어 있다. (1-3-2)


step 2) 정렬된 간선을 순서대로 선택한다.  ->  정점 = 3, 4, 가중치 = 6


step 3) 3, 4은 연결되어 있지 않으므로, 선택된 간선을 통해 연결한다. ->  정점 = 3, 4, 가중치 = 6



step 2) 정렬된 간선을 순서대로 선택한다.  ->  정점 = 2, 4, 가중치 = 7


step 3) 2, 4은 연결되어 있다.. (2-3-4)


step 2) 정렬된 간선을 순서대로 선택한다.->  정점 = 4, 6, 가중치 = 8


step 3) 4, 6은 연결되어 있지 않으므로, 선택된 간선을 통해 연결한다. ->  정점 = 4, 6, 가중치 = 8



-> 모든 정점이 연결되었으므로 최소 스패닝 트리가 완성되었습니다.




4. 크루스칼 알고리즘의 구현


 이제 다음 알고리즘을 구현해보겠습니다.


step 0) 모든 간선을 끊어 놓는다.

step 1) 가중치 순으로 간선들을 정렬한다. (오름차순)

step 2) 정렬된 간선을 순서대로 선택한다.

step 3) 선택한 간선의 두 정점이 연결되어 있지 않으면, 해당 간선을 최소 스패닝 트리에 포함 시키고 두 정점을 연결한다.

              ( 1-2-3 처럼 간접적인 연결이어도 1,3 은 연결되어 있는 걸로 친다.)


step 0) 모든 간선을 끊어 놓는다.

-> 미리 연결시켜 놓지 않기 때문에, step 0을 구현할 부분은 없습니다.


step 1)
 가중치 순으로 간선들을 정렬한다. (오름차순)

-> 간선 정렬은 STL sort함수를 통해 할 수 있습니다. 시간복잡도는 O(E log E)가 됩니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
#include<vector>
 
using namespace std;
 
const int N = 100005;
 
struct edge{
    int v1, v2, cost;
    bool operator < (const edge& e1) constreturn cost < e1.cost; }
};
vector<edge> e;
 
int main(){
    /*
    간선 입력 부분
    */
    sort(e.begin(),e.end());
    return 0;
}
cs


step 2) 정렬된 간선을 순서대로 선택한다.


1
2
3
4
5
6
7
8
//code by RiKang, weeklyps.com
int kruskal(int kn){
    sort(e.begin(),e.end());
    for(auto now: e){
        // now = e[0] ~ e[e.size()-1] 까지 순회합니다.
    }
    return ret;
cs


step 3)
 선택한 간선의 두 정점이 연결되어 있지 않으면, 해당 간선을 최소 스패닝 트리에 포함 시키고 두 정점을 연결한다.


 step 3에서 필요한 연결을 확인하는 작업연결하는 작업은 유니온 파인드로 관리하면 쉽게 할 수 있습니다. 크루스칼 알고리즘에선 정점의 연결만 있고, 끊는 건 없기 때문이지요.


연결을 확인하는 작업 : 두 정점이 같은 집합에 속하는 지로 판별합니다. (find)

연결하는 작업 : 유니온 파인드의 병합 연산으로 해결합니다. (union)


1
2
3
4
5
6
7
8
9
10
11
12
13
//code by RiKang, weeklyps.com
int kruskal(int kn){
    uf.init(kn+1);
    sort(e.begin(),e.end());
    int ret = 0;     // 간선 가중치의 합의 최솟값
    for(auto now: e){
        if(!uf.same_set(now.v1,now.v2)){ // 두 정점이 끊어져 있는가?
            ret+=now.cost;       // 가중치를 ret에 더함
            uf.merge(now.v1,now.v2); // 두 정점 연결
        }
    }
    return ret;
}
cs


 유니온 파인드는 O(E log E) 보다 빠르므로 크루스칼의 최종 시간 복잡도는 O(E log E)가 됩니다. E <= V^2 임이 보장되는 평범한 그래프라면 O(E log V)라고 할 수 있습니다.




5. 크루스칼 알고리즘 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
#include<vector>
 
using namespace std;
 
const int N = 100005;
// 유니온 파인드 시작
struct union_find_tree{
    vector<int> parent;
    vector<int> height;
    vector<int> group_size;
 
    void init(int uf_n){
        parent.clear(), height.clear();
        group_size.clear();
        for(int i=0; i<uf_n; i++){
            parent.push_back(i);
            height.push_back(0);
            group_size.push_back(1);
        }
    }
 
    int get_root(int now){
        if(parent[now]==now) return now;
        return parent[now] = get_root(parent[now]);
    }
    
    bool same_set(int v1, int v2){
        return get_root(v1)==get_root(v2);
    }
 
    void merge(int v1,int v2){
        v1=get_root(v1), v2=get_root(v2);
        if(v1==v2) return;
        if(height[v1] < height[v2]) swap(v1,v2);
        parent[v2]=v1;
        group_size[v1]+=group_size[v2];
        if(height[v1]==height[v2])
            height[v1]++;
    }
}uf;
// 유니온 파인드 끝
 
struct edge{
    int v1, v2, cost;
    bool operator < (const edge& e1) constreturn cost < e1.cost; }
};
vector<edge> e;
 
int kruskal(int kn){
    uf.init(kn+1);
    sort(e.begin(),e.end());
    int ret = 0;     // 간선 가중치의 합의 최솟값
    for(auto now: e){
        if(!uf.same_set(now.v1,now.v2)){ // 두 정점이 끊어져 있는가?
            ret+=now.cost;       // 가중치를 ret에 더함
            uf.merge(now.v1,now.v2); // 두 정점 연결
        }
    }
    return ret;
}
 
int main(){
    /*
    간선 입력 부분
    */
    int ans = kruskal(N);
    return 0;
}
cs




6. 문제


(0) [BOJ 1922] 네트워크 연결



(1) [BOJ 1647] 도시 분할 계획



(2) [BOJ 2887] 행성 터널




7. 크루스칼 알고리즘의 정당성


 크루스칼 알고리즘이 최소 스패닝 트리를 찾는다는 걸 증명해보도록 하겠습니다. 크루스칼 알고리즘은 그리디 패러다임에 속하며 많은 그리디가 그렇듯이, 귀류법으로 증명 가능합니다.


귀류법 ) 크루스칼 알고리즘 결과가 MST 가 아니라고 해보겠습니다. ...(1)


T = 크루스칼로 선택된 간선들의 그래프


 위와 같이 T를 정의하면, 크루스칼이 시작할 때 T에는 간선이 하나도 없습니다.

 크루스칼이 진행됨에 따라, 간선이 하나씩 선택되면서 T에 포함되게 되지요.

 크루스칼이 끝났을 때 T는 스패닝 트리이면서 최소 스패닝 트리는 아니게 될 것입니다.( (1)에 의해 크루스칼 알고리즘의 결과가 MST가 아닌 경우를 이야기하고 있습니다.)


 이제 크루스칼이 시작할 때의 T를 T-init, 크루스칼이 끝났을 때의 T를 T-last라고 하면, 아래의 명제가 참이 됩니다.



 T-init은 공집합이기 때문에 MST의 부분 그래프였지만,

 T-last는 MST가 아닌 스패닝 트리이기 때문에 MST의 부분 그래프가 되는 것이 불가능합니다.


 따라서 크루스칼 알고리즘상 선택된 순간, T가 MST의 부분 그래프가 되는 것이 불가능하도록 만든 간선 (u,v)가 존재해야 합니다. T는 간선의 삭제가 없고 추가만 있기 때문에, 이런 (u,v)가 존재해야 함을 증명할 수 있습니다.

 다시 말하면, 크루스칼의 진행 과정 속에는 아래의 조건을 만족하는 T와 MST가 존재해야 합니다.



 이제 (u,v) 를 선택하기 직전의 T를 부분그래프로 가지는 MST 중 하나를 생각해 보겠습니다. ( (u,v) 이전의 크루스칼 간선들을 모두 포함한 MST ) 그러면 이 MST 에서는 (u,v) 가 직접 연결되어 있지 않고 간접적으로 연결되어 있습니다.


 그런데 MST 에서 u 와 v 를 연결하는 경로에는 정렬된 간선 배열에서 (u,v) 보다 뒤에 있던 간선이 무조건 하나 이상 포함되어야 합니다. (u,v) 가 크루스칼에서 선택되었다는 건 '(u,v) 앞의 간선을 모두 연결해도 u,v는 연결되지 않는다.' 는 의미도 되기 때문이지요.


 이 때, MST에 포함된, 정렬된 간선 배열에서 (u,v) 보다 뒤에 있던 간선을 삭제하고 (u,v) 를 추가하면 스패닝 트리가 유지되면서 코스트는 MST 이하인 트리가 완성됩니다.


 삭제한 간선의 코스트 >= (u,v) 코스트 이며,

 삭제한 간선의 두 정점도 (u,v) 를 경유하면 연결되기 때문에 스패닝 트리도 유지되기 때문입니다.

 그런데, 코스트가 MST 이하인 트리도 MST 일 수 밖에 없습니다. 그리고 이 트리는 이 식도 만족하는 MST입니다. 삭제한 간선은 (u,v)보다 뒤에 있던 간선이기 때문이지요.


결국, (u,v) 를 포함한 MST 를 찾았습니다. 이 결과를 거슬러 올라가면 (1) 에 모순입니다.



※ 본문의 코드들은 C++ 17 환경에서 작성되었습니다.

※ 문의 : rikang93@gmail.com


반응형

'그래프 ( Graph )' 카테고리의 다른 글

프림 알고리즘 ( Prim's algorithm )  (1) 2017.11.28
트리의 지름  (0) 2017.11.25
유니온 파인드 ( Union-find )  (0) 2017.11.21