개념 - 가중치 그래프, MST(Kruskal, Prim)

출처 : c++로 쉽게 풀어쓴 자료구조

가중치 그래프 weighted graph

간선에 비용이나 가중치가 할당된 그래프. G = (V, E, w)에서 w(e)는 간선 e의 강도(weight), 비용(cost), 길이(length)라고 부른다. 

어떤 가중치 그래프의 경로 p = (v0, v1, v2, ... vk)라고 할 때 w(p)는 각 경로의 가중치의 합이다. (1부터 k까지의 e(vi - 1, vi)의 합)

용도

여러 선택지중 가장 빠르고 효율적인 길을 찾을 때 쓰이므로 넓은 응용분야에서 사용된다.

가중치의 표현

일반 그래프에서 간선의 유무를 1,0을 나타내던 배열을 사용할 수 있다. 이 때 가중치가 유효한 값 범위를 갖는다면 해당 값을 벗어난 값을 간선이 없다는 뜻으로 사용할 수 있다. 

최소 비용 신장 트리 MST : minimum spanning tree

신장트리란 그래프 내의 모든 정점을 포함하는 트리(사이클이 없는 연결그래프)다. 하나의 그래프에는 여러 신장 트리가 있을 수 있다.

모든 정점을 경유하는 통신망(신장트리)를 건설할 때 비용, 시간, 길이 등을 최대한 효율적인 경로로 건설해야할 것이다. 이 때 MST가 유용하게 쓰인다. minimum spanning tree! 이 때 간선은 두 정점을 연결하는 비용이 된다. MST의 조건은 다음과 같다.

1. 간선의 가중치의 합이 최소여야 한다.

2. 반드시 N - 1개의 간선을 사용한다.

3. 사이클이 포함되서는 안된다.

Kruskal의 MST 알고리즘

크루스칼의 알고리즘은 탐욕적 방법(greedy method)을 사용한다. 이는 해당 순간에 최적이라고 생각되는 선택을 모아서 최종적인 답을 만드는 방법이다. 결과가 항상 최적이라는 보장은 없지만, 크루스칼의 알고리즘은 최적해를 주는 것으로 증명되었다.

자연어로 나타낸 크루스칼의 알고리즘

1. 그래프의 모든 간선을 가중치에 따라 오름차순 정렬한다.

2. 가장 가중치가 작은 간선 e를 뽑는다.

3. e를 신장 트리에 넣을 경우 사이클이 생기면 삽입하지 않고 2번으로 이동한다.

4. 사이클이 생기지 않으면 최소 신장 트리에 삽입한다.

5. n - 1 개의 간선이 삽입될 때까지 2번으로 이동한다.

사이클이 생기는지를 검사하는 방법은, 간선의 양 끝 정점이 같은 집합에 속하는지 검사하는 것이다.

union-find 연산

union(x, y)는 x와 y가 속해있는 집합을 받아 합집합을 만드는 연산이다.

find(x)는 x가 속해있는 집합을 반환하는 연산이다.

{1}, {2}, {3}, {4}, {5}, {6}

 이 있을 때 union(1, 4)와 union(5, 2)를 하면 다음과 같아진다.

{1, 4}, {5, 2}, {3}, {6}

find(2)를 하면 5,2가 반환된다. 이제 union(4,5)와 union(3,6)을 하면

{1,4,5,2} {3,6}이 된다.

정점 집합 역시 비트 벡터, 배열, 연결리스트 등으로 구현할 수도 있지만 가장 효율적인 방법은 tree다.

책에서는 배열로 union과 find를 하는 방법을 사용하는데 생소해서 이해하는데 오래걸림. 신기하다.

크루스칼 알고리즘의 시간복잡도는 n개의 간선을 정렬하는데 필요한 O(nlogn) (힙을 사용하기 때문에)

구현 : http://kid5.tistory.com/288

Prim 알고리즘

http://kid5.tistory.com/289