최소 비용 신장 트리 (2)

Minimum Spanning Tree

Kruskal Algorithm

서로소인 집합들의 표현

- 각 집합을 하나의 트리로 표현한다.

- disjoint 특성(두 집합이 공집합)을 가진 sets - find(u)=u가 속한 집합 찾기, union(u, v)=두 집합을 하나로 합치기

- Ex) 2개의 집합

- 리프 노드로부터 루트 노드까지 따라 올라가면서 연산을 수행한다. 이 때 각 노드는 자식 노드가 아닌 부모 노드의 주소를 가지기 때문에 링크 구조를 쓰지 않아도 좋다. 또한 부모 노드의 주소가 자신의 주소와 동일하다면 그 노드는 루트 노드라는 것을 뜻한다.

- 트리의 모양은 크루스칼의 진행에 따라 얼마든지 바뀔 수 있다.

- 여러 트리가 있어도 모두 한 개의 배열로 표현이 가능하다. 이때 배열은 상향식으로 표현하며 각 인덱스의 데이터에는 부모 노드를 표시하게 된다. 이것이 가능한 이유는 모든 노드의 부모가 유일하기 때문이다. (자식을 표시하는 하향식으로 구성할 경우 자식이 유일하지 않기 때문에 하나의 배열로 표현하는 것이 불가능해진다.)

Find-Set (v)

- 자신이 속한 트리의 루트를 찾는 메소드

- 슈도 코드

FIND-SET (x) // x가 속해있는 트리의 루트 노드 이름을 반환하는 것이 목표이다.

if x != p[x]

p[x] = FIND-SET(p[x]) // 순환적으로 구성

return p[x];

-> 시간 복잡도는 O(h)가 된다. h는 트리의 높이이며 최악의 경우 높이를 구하는데 O(n)의 시간이 걸린다.

while x != p[x]

x = p[x];

return p[x];

union (u, v)

- 한 트리의 루트를 다른 트리 루트의 자식 노드로 만드는 메소드

- 둘 중 하나를 다른 쪽에 붙이면 되기 때문에 위 그림에서 c를 f에 붙이는 것이 아니라 f를 c에 붙이는 것도 가능하다.

- 슈도 코드

UNION (u, v)

x = FIND-SET(u);

y = FIND-SET(v);

p[x] = y;

-> 루트 노드를 찾은 이후에는 O(1)의 시간만이 걸리지만, 루트를 찾는 데 O(h)만큼의 시간이 소요된다.

weighted-union (u, v)

- 두 집합을 결합할 때 작은 트리의 루트를 큰 트리 루트의 자식으로 만든다. (크기는 노드의 개수를 의미한다.)

- 각 트리의 크기를 꾸준히 세주고 있어야 노드의 개수를 알기 쉽다.

- 슈도 코드

WEIGHTED-UNION (u, v)

x = FIND-SET (u);

y = FIND-SET (v);

if (size[x] > size[y])

p[y] = x; // 작은 트리를 큰 트리에 넣는다 (작은 트리의 부모 노드를 큰 노드의 루트 노드로 지정하여 실현)

size[x] += size[y];

else

p[x] = y;

size[y] += size[x];

Worst와 Weighted Union

- weighted union의 효과를 쉽게 알 수 있는 그림

- weighted union을 사용하면 트리의 높이가 $log{n}$을 넘지 않는다. 

Path Compression (경로 압축)

- find 메소드에서 행하는 트릭이다. 트리를 루트까지 되짚어 올라가는 동안 부모 노드들을 각각 떼어내 루트 노드에 따로 붙이게 되는 기술이다.

- 지나가지 않는 노드들은 건들이지 않고 오직 지나갔던 조상 노드들만 따로따로 분해한다.

- 슈도 코드

FIND-SET-PC (x)

while x != p[x]

p[x] = p[p[x]]; // 완전히 압축되는 결과는 없지만 절차를 절반정도 줄여주는 효과를 준다.    

x = p[x];

return p[x];

-> 시간 복잡도의 측면에서 봤을때는 p[p[x]]를 통해 두 레벨씩 올라가는 것보다는 while을 두 번 사용하여 압축을 수행하는 것이 더 효율적이다.

Weight Union with Path Compression (WUPC)

- M번의 union-find연산의 총 시간 복잡도는 O(N + Mlog*N)이 된다. (N은 원소의 개수를 뜻하며 log*n은 1이 될때까지 log를 반복하여 취하는 횟수를 뜻한다.)

- 거의 선형 시간을 소요하는 작업이다. 즉 한 번의 find 혹은 union이 거의 O(1) 시간만 소요한다.

Kruskal알고리즘의 시간 복잡도

- 실질적으로 엣지들을 가중치순으로 정렬하는 데 걸리는 시간이 가장 오래 걸린다.

- m은 $O(n^2)$이다.

- Initialize A : O(1)

- First for loop : |V| MAKE-SETs => O(n)

- Sort E : $O(|E|log_2{|E|})$ => $O(mlogm)$

- Second for loop : O(|E|) 2 FIND-SET and 1 UNION (둘 다 O(1)에 가까운 시간) => O(m)

- 총 시간 복잡도 : $O(|E|log_2{|E|})$ => $O(mlogm)$ = $O(mlogn)$

Prim

Prim Algorithm

- 임의의 노드를 출발노드로 선택한다.

- 출발 노드를 포함하는 트리를 점점 키워나간다.

- 각 단계에서 이미 트리에 포함된 노드와 포함되지 않은 노드를 연결하는 엣지들 중에 가장 가중치가 작은 엣지를 선택한다.

- $V_A$ : 현재 엣지들에 의해 연결되며 만들어진 트리에 속한 노드

- |$V_A$| = n이면 모든 노드들이 연결되었다는 것을 뜻하기 때문에 프로그램을 종료하게 된다.

- 최악의 경우 각 노드를 구하는 데 소요되는 시간은 O($n^2$) X (n - 1) = O($n^3$)이다. 단순하게 생각하고 구현했을 경우 효율이 떨어지는 결과가 나오기 때문에 프림 알고리즘은 시간 복잡도를 줄이는 데 무게를 많이 두어야 한다.

Prim을 통해 MST가 찾아지는 이유

- Prim 알고리즘의 임의 한 단계를 본다.

- A를 현재까지 알고리즘을 진행하며 선택한 엣지들의 집합이라 하며 A를 포함하는 MST가 존재한다고 하자. (이 가정이 가능한 이유는 처음 A가 공집합으로 시작하기 때문이다.)

- S와 V-S 두개의 컷이 있다고 할 때 어느 엣지들도 이 두 컷을 모두 지나는 상태는 없다. 프림 알고리즘이 선택한 엣지는 두 컷을 통과하는 엣지들 중 가중치가 가장 작은 엣지이며 또한 이는 집합 A에 대해 안전한 엣지이기도 하다. 그렇기 때문에 알고리즘이 선택한 엣지를 포함하더라도 MST를 벗어나지 않게 된다.

- 엣지 (u, v)는 출발 노드에 이미 연결된 노드와 그렇지 않은 노드를 연결하는 엣지들 중 가장 가중치가 작은 엣지이다.

가중치가 최소인 엣지 찾기

- $V_A$ : 이미 트리에 포함된 노드들

- $V_A$에 아직 속하지 않은 각 노드 v에 대해 아래와 같은 값을 유지한다.

1) key(v) : 이미 $V_A$에 속한 노드와 자신을 연결하는 엣지들 중 가중치가 최소인 엣지 (u, v)의 가중치값

2) π(v) : 선택한 엣지 (u, v)의 끝점인 u

- 이 방식을 통해 프림 알고리즘을 수행하게 된다면 키값이 최소인 노드를 찾는데 O(n)시간만이 소요되게 된다는 장점이 있다.

- 키 값을 계산하는 데 걸리는 시간또한 구해야 한다. 각 키의 값들은 출발점과 연결하는 엣지가 있으면 그 엣지로 초기화하며, 없다면 무한대로 초기화해놓는다.

- 새 엣지를 등록하면 주변 노드들의 키값을 갱신하게 되는데 노드들의 키값을 완전히 버리는 것이 아니라 새로 등록된 노드와 연결된 노드들의 키값만 새로 비교한다. 더 작은 가중치값이라면 교체하면 된다.

- 노드들의 가중치들을 갱신하는 시간 O(n) X 모든 노드들을 연결시키기 위한 반복 (n - 1) = O($n^2$)의 시간이 소요된다.

프림 알고리즘의 슈도 코드

MST-PRIM (G, w, r) // r은 출발점을 뜻한다.

for each u ∈ V

key[u] = ∞;

π[u] = null;

$V_A$ = {r};

key[r] = 0;

while $V_A$ < n // while문은 n-1번 반복한다.

find u  $V_A$ with the minimum key value; // 최소값을 찾는 과정이며 O(n)시간이 걸린다.

$V_A$ = $V_A$ ∪ {u};

for each v  $V_A$ adjacent to u // degree(u) = O(n)

if key[v] > w(u, v)

key[v] = w(u,v);

π[u] = u;

-> 이 코드의 시간 복잡도는 O($n^2$)가 된다.

key값이 최소인 노드 찾기

- 우선순위 큐 (Minimum Priority Queue)를 이용한다.

$V-V_A$에 속한 노드들을 저장한다.

Extract-Min : key값이 최소인 노드들을 삭제하고 반환한다.

- O(logn)시간 내에 최소값을 찾을 수 있게 된다.

- 슈도 코드 

MST-PRIM (G, w, r)

for each u ∈ V[G]

key[u] = ∞;

π[u] = null;

key[r] = 0;

Q = V[G];

while Q != {} // 공집합이 아닐때

u = EXTRACT-MIN (Q) // 최소값을 찾는 과정으로 O(logn)의 시간이 걸린다.

for each v ∈ Adj[u]

if v ∈ Q and w(u, v) < key[v]

π[v] = u;

key[v] = w(u, v); //우선순위 큐에서 키값을 감소시키는 명령으로 O(logn)시간이 걸린다.

프림 알고리즘의 시간 복잡도

- 이진 힙을 이용하여 우선순위 큐를 구현할 경우

- while 반복

1) n번의 Extract-Min 연산 : O(nlogn)

2) m번의 Ddecrease-Key 연산 : O(mlogn)

- 시간 복잡도는 1) + 2) = O(mlogn)

- 우선순위 큐를 사용하지 않고 단순히 구현할 경우 : O($n^2$)

- 피보나치 힙을 사용하여 구현한다면 O(m + nlogn)의 시간으로도 구현할 수 있다.