그래프로 모델링 되는 문제들을 해결하기 위한 알고리즘들이 나온다.

여기에 소개되는 알고리즘인 Prim, Kruskal, Dijkstra 알고리즘은

Greedy Algorithm의 대표적인 예이다.

특히, 이 알고리즘들은 일반적으로 최적의 해를 구하지 못하는

Greedy Algorithm에서 최적의 해를 구하는 알고리즘이다.


1. 최소(비용) 신장 트리(Minimum Spanning Tree)

먼저 신장트리의 의미를 알아보자.

신장(伸張)이라는 단어의 의미를 네이버 국어사전에서 찾아보면,

"세력이나 권리 따위가 늘어남. 또는 늘어나게 함."

그래도 역시 감이 안 온다. 위키피디아에 있는 정의를 찾아보자.

Undirected Graph에서 그 Graph의 부분Graph이면서 모든 꼭지점을 연결하는 트리이다..

즉 Cycle 이 없는, 모든 Vertex를 포함하는 부분 Graph를 말한다.

하나의 Graph에는 많은 Spanning Tree가 있을 수 있다.

Edge에 Weight가 있을 때, Spanning Tree 중 Weight가 최소인 것을 바로

"Minimum Spanning Tree"(이하 MST) 라고 하는 것이다.


그래서, 이 MST를 찾는 알고리즘에는 Prim Algorithm과 Kruskal Algorithm이 있다.

두 Algorithm 모두 Greedy Algorithm 이지만, 모두 정확한 MST를 찾아낸다.

(실제 C 언어로 밑바닥부터 구현해 보니 설명처럼 쉽진 않았다.)



- Prim Algorithm

( http://en.wikipedia.org/wiki/Prim%27s_algorithm )


(위키피디아에 있는 구현 아이디어)

Graph G(V,E)가 있을 때,

최초에 V' = { x }, (x 는 V 에 있는 임의의 Vertex). E' = { } 로 둔다.

V = V' 가 될 때까지 다음을 수행한다.

1. E 로 부터 최소의 가중치를 갖는 간선 (u,v)를 고른다.

   (단, u 는 V' 에 포함되고 v 는 V' 에 포함되지 않아야 한다.)

2. v 를 V'에 추가한다. (u,v) 를 E' 에 추가한다.

위의 과정을 반복이 끝나면, G(V', E')가 MST가 된다.


위의 방법은 위키피디아에 되어 있는 아이디어이다.

실제 책에는 좀 다른 방법으로 구현하는데,

아래 적은 내용은 책과 완전 동일한 것은 아니다.(하지만 거의 비슷하다)

(책에 있는 구현 아이디어)

Graph G(V,E)가 있을 때,

Vertex2 는 원래 Vertex 정보에 key(가중치정보), color(방문정보) 값, parent 값이 추가된 정보다.

모든 Vertex 에 대하여 Vertex2를 만든다. Vertex2 의 집합을 V2 라고 한다.

이 때, Vertex2 들의 기본값은 key = 무한대, color = 미방문, parent = NULL 이다.


최초에 V' = { x }, (x 는 V2 에 있는 임의의 Vertex). E' = { } 로 둔다.

시작점 x 의 key = 0, color = In_Heap 로 설정하고, x 를 key 값에 대한 Min-Heap, 'H' 에 넣는다.

H 가 Empty 가 될 때까지 아래를 반복한다.

1. H 의 Root 값 r 을 가져오고, r 을 V2 에서 제거한다.

2. r 의 color 를 방문함으로 설정하고, V' 에 추가한다.

3. r 과 r's parent 를 연결하는 Edge 를 E' 에 추가한다.

4. r 의 인접 Vertex 들 각각에 대하여 Vertex 'v'의 color 가 미방문이라면,

   key값과 Edge 'e'의 weight 를 비교하여,

   'e' 의  weight 값이 작다면, 'v' 의 key 값을 'e' 의 weight 값으로 설정하고,

   'v' 에 대하여 V2 를 Reheapfy 한다.

   그리고 'v' 의 parent 를 r 로 설정한 뒤,

   'v' 의 color 가 '미방문' 이라면 'v' 의 color = In_Heap 으로 설정하고 'H' 에 Insert 한다.

위의 과정을 반복이 끝나면, G(V', E')가 MST가 된다.


아래에 있는게 좀 더 복잡해 보이지만, 내가 직접 구현했던 방법이라

오히려 자세하게 설명하느로 길어진 것으로 판단된다.


Graph를 어떻게 구현하는냐에 따라 Time Complexity가 다른데,

Matrix로

 O(V^2)
 Binary Heap + Adjacency List  P((V+E) log V) = O(E log V)
 Fibonacci Heap + Adjacency List  O(E + V log V)

이와 같다.


- Kruskal Algorithm

( http://en.wikipedia.org/wiki/Kruskal%27s_algorithm )


Minimum Spanning Tree를 찾는 다른 Greedy Algorithm이다.

이 알고리즘의 구현에 대해선 따로 설명하지 않겠다. 위키피디아 참고.


단, Prim 과 차이점을 잠깐 살펴보겠다.

Kruskal 의 Time Complexity 는 O(E log E) 인데,

E <= V^2 이므로 O(E log V^2) = O(2E log V) = O(E log V)가 된다.

Prim 의 피보나치힙을 사용한 구현과 비교했을 때,

V, E 가 큰 경우,

E 의 값의 크기에 따라 Prim 의 피보나치힙 / Prim 의 바이너리힙 or Kruskal 알고리즘

을 택하면 될 것으로 보인다.


Prim 과 Kruskal 어떤 것을 구현해 볼까 고민하다가,

Kruskal 은 쉬워 보이긴 하지만,

Cycle 체크가 필요한 코드가 있기에 패스.

(힙도 구현해야 되고 Cycle 체크까지 해야 되기에...)


일단 이 글은 여기까지.

그 이름도 유명한 Dijkstra 알고리즘과 TSP 문제는 다음 글에...


p.s

계속 느끼는 거지만, 이미 잘 만들어진 Library 가 있는데,

C 로 맨땅에서 만드는 건 어렵네.

(앞에서 만들어 둔 자료구조들을 대충 아무렇게나 던줘놨더니... 찾질 못하겠음...)

 











반응형

설정

트랙백

댓글