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

Kruskal Algorithm과 Prim Algorithm은 Greedy Algorithm를 적용하는 알고리즘 중의 하나이다. 최소신장트리를 구성할 때, 최적의 해를 구하려면 가중치를 낮은 간선을 선택하는 것이 좋다. 그래서 고안된게 바로 크루스칼 알고리즘이다.

크루스칼 알고리즘은 각 단계에서 가중치가 작은 간선부터 선택한다.

선택하는 과정에서 사이클이 만들어질 경우 그 간선은 선택하지 않는다.

그리고, 신장트리는 n개의 정점을 가질 때, 반드시 n-1개의 간선을 가지게 되어있으므로 간선이 n-1개가 되면 종료하면 된다.

크루스칼 알고리즘은 다음과 같은 사항을 고려해야한다.

1. 가중치가 작은 간선을 선택하는 데는 많은 시간이 소요되므로 모든 간선을 오름차순으로 정렬

2. 깊이우선탐색(DFS), 너비우선탐색(BFS)을 이용하여 사이클이 만들어지는지 확인(방문한 정점을 또 방문했는지를 확인)

크루스칼은 (프림처럼, 나중에 배우겠지만) 트리를 유지하며 만들어지는 것이 아니라, 트리를 마구 생성하여 잇는 기법이기 때문에 임의의 정점이 선택됬을 때, 그 정점이 어느 집합의 원소인지를 알아내는 연산이 추가적으로 필요하다.

1. init_set 연산 : 최초의 정점 하나를 원소로 하는 집합

2. find 연산 : 임의의 정점이 어느 집합의 원소인지를 알아내는 연산

3. union 연산 : 두 집합을 하나로 합치는 연산

다음은 크루스칼 알고리즘의 실행과정이다.

(출처 : http://cbb1225.tistory.com/entry/%EC%B5%9C%EC%86%8C-%EC%8B%A0%EC%9E%A5-%ED%8A%B8%EB%A6%ACMinimum-Cost-Spanning-Trees)

// 중간중간 사이클이 생기는지를 검사

(a) : 상태는 간선들의 가중치를 나타낸 그래프

(c) : (b)상태에서 가장 가중치가 낮은 값은 10이므로 (0, 5)를 선택

(d) : 그 다음으로 가중치가 낮은 값인 12, (2, 3)을 선택

(e) : 그 다음으로 가중치가 낮은 값인 14, (1, 6)을 선택

(f)  : 가중치 16, (1, 2) 선택

(g) : 그 다음으로 가중치가 낮은 값이 18이지만, (3, 6)을 선택할 경우 사이클이 생기므로 간선을 버리고, 그 다음 가중치 22(3, 4)를 선택

(h) : 가중치 24, (4, 6)를 선택할 경우 사이클이 생기므로, 가중치 25를 선택, 간선의 총 갯수가 정점의 갯수보다 1개 작으므로 종료

* Kruskal Algorithm *

edge_set kruskal_MST(edge_set E, int n){

sort(E); // 모든 간선을 오름차순으로 정렬

edge_set MST_E = { };

for(i = 0; i<n; i++) init_set(i); // n개의 집합(트리)를 생성

while(MST_E의 간선 수 < n-1) // 종료조건 명시

(u, v) = E의 최소 가중치 간선;

E = E - {(u, v)};

if(find(n) != find(v)){ // u와 v가 다른 집합(트리)의 원소인지 확인

MST_E = MST_E U {(u, v)};

union(u, v); // 두 집합을 합병하는 연산

}

}

return MST_E;

}

크루스칼의 알고리즘은 최소의 가중치를 갖는 간선을 선택했고, 임의의 간선을 선택하는 과정에서 트리가 마구 생성되었다. 반면 이제 배울 프림 알고리즘은 역시나 가중치가 낮은 간선부터 선택한다. 하지만 트리를 마구 여기저기서 생성하는 것이 아니라, 트리를 유지하면서 완성시켜가는 성질을 갖고있다.

즉, 트리를 처음부터 끝까지 유지하게된다.

확실히 글보다 그림으로 이해하는 것이 빠르기 때문에 아래 그림을 참고하도록 한다.

(출처 : http://cbb1225.tistory.com/entry/%EC%B5%9C%EC%86%8C-%EC%8B%A0%EC%9E%A5-%ED%8A%B8%EB%A6%ACMinimum-Cost-Spanning-Trees)

(a) 임의의 간선을 선택한다 (2, 3)

(b) 단계 (a)에서 선택한 간선의 정점으로부터 가장 낮은 가중치를 갖는 값을 비교하여 정점을 선택하여 간선을 잇는다. (1, 2) => (16 < 18 < 22)

(c) 정점 1, 2, 3에서 연결된 간선들의 가중치 28, 14, 22, 18 중에서 가장 낮은 14를 선택하여 간선을 잇는다. (1, 6)

(d) 정점 1, 2, 3, 6에서 연결된 간선들의 가중치 18, 24, 28, 22 중에서 가장 낮은 값인 18을 선택한다, 하지만 18을 선택할 때 사이클이 생기므로 폐기하고, 그 다음 값인 22를 선택하여 잇는다. (3, 4)

(e) 정점 1, 2, 3, 4, 6에서 연결된 간선들의 가중치 24, 18(폐기됨), 25, 28 중에서 가장 낮은 값인 24를 선택한다. 하지만 또 사이클이 생기므로 폐기하고, 25를 선택하여 잇는다. (4, 5)

(f) 정점 1, 2, 3, 4, 5, 6에서 연결된 간선들의 가중치 28, 18(폐기됨), 24(폐기됨), 10 중에서 가장 낮은 값인 10을 선택한다. 이 때 간선들이 정점보다 1개 적으므로 종료한다.

* Prim Algorithm *

edge_set prim_MST_1(edge_set E, vertex s){

edge_set MST_E = { }; // 초기화 

vertex_set MST_V = { s }; // 시작점 설정

loop(n-1) // n-1번 방복

(u, v) = E의 최소 가중치 간선, 단 u ∈ MST_V, v !∈ MST_V; // 같은 vertex면 안됨

MST_E = MST_E U (u, v) // 검증된 간선을 추가

MST_V = MST_V U v; // 검증된 정점을 추가

}

return MST_E;

}

크루스칼 알고리즘과 다르게 프림 알고리즘은 사이클이 존재하는지를 검사하는 부분이 없다.

( 단 u ∈ MST_V, v !∈ MST_V;  -> 이부분은 단순히 (u, v)의 조건을 명시해준 부분이다.)

그렇다면 프림의 알고리즘은 사이클을 생성하지 않는다는 의미가 되는데, 예를 들어 살펴보자.

X, Y, V 라는 정점들이 있고,  (X, Y)와 (Y, V)는 연결된 상태에서 (X, V)를 선택한다고 가정했을 때, 사이클이 생기게 된다. 하지만, 프림 알고리즘은 정점을 선택하여 간선을 이으며 트리를 유지해나가기 때문에,

즉, 다른말로 말하면 트리를 유지하는 과정에서 정점과 간선을 선택할 때 이미 이 두가지는 최소 신장 트리에 포함하는 과정을 거치게 된다.

그렇기 때문에 애초부터 최소 신장 트리에 포함되어 있기 때문에 (X, V)는 선택할 수가 없게 된다.

쉽게 말해서 트리를 처음부터 끝까지 유지하며 생성되는 기법이기 때문에, 다시 거슬러 올라가 정점을 이을 순 없다는 얘기이다.

크루스컬 알고리즘에서는 트리를 끝까지 유지하지 않고, 여기저기서 트리가 생성되고 나중에 하나씩 합쳐지는 형태이기 때문에  합쳐지는 과정에서 사이클이 마구 생길 수 있기에 반드시 사이클이 생기는지 검사를 해줬어야했다.

그리고, 중요한 것은 위와 같은 알고리즘을 구현하는데 있어서 파란색으로 표시한 줄에서 최소 가중치의 간선을 선택하는 방법이 성능을 좌우하게 된다. (모든 경우를 따져가며 선택하기에..), 그래서 모든 간선들에 대해서 최소 가중치를 조사하는 것은 알고리즘 측면에서는 시간낭비라고 할 수 있다.

그래서 각도를 바꾸어 생각해보면 정점을 기준으로 생각해보록한다. (그림에서 살펴볼땐 정점에 연결된 값을 기준으로 선택하였다, 앞으로 볼 내용이 그내용이고 원랜 선택가능성이 있는 간선을 모두 조사하는 것이였음!!)

연결그래프에서는 보통 정점의 수가 간선의 수보다는 적으므로 각 정점 별로 최소 가중치를 관리하는 편이 성능상으로 볼 때 나이스하다고 볼 수 있다.

이를 위해 최소 신장 트리에 포함되지 않은 각 정점 v에 대해 distance(v)와 nearest(v)를 정의한다.

distance는 이미 최소 신장 트리에 속한 정점과 v사이의 간선 가중치 중 최소값이며, nearest는 그 때의 최소 신장 트리의 정점이다.

개선된(?) 프림 알고리즘은 시간 날 때 다시 작성하는걸로~~