15-4. 최소비용신장트리( Minimum Spanning Tree)

• Prim의 알고리즘

- 임의의 노드를 출발노드로 선택

- 출발 노드를 포함하는 트리를 점점 키워 감

(크러스칼은 에지들의 가중치가 작은 순서대로 접근하는 방법이었다면, 프림은 출발노드부터 연결 연결된 노드들을 탐색하여 트리를 키운다)

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

Prim 알고리즘

 

위의 그래프에서 출발 노드가 초록색 노드라고 하면, 출발 노드에 인접한 노드들을 A라 하면, 그 부분트리에 포함된 노드들의 집합은 V of A(빨간 노드들)라 하자.

 

 

Prim 알고리즘 1

Prim 알고리즘 2

 

(a) : 출발노드 a 에서 인접한 노드 b와 노드 k 가 있다. 가중치가 작은 에지는 4이므로 노드 b를 선택한다.

(b) : 이제 노드 a 와 노드 b는 V of A의 부분집합이 되었다.

(c) : 노드 a에 인접한 노드 k와 노드 b에 인접한 노드 c가 있다. 각 에지의 가중치는 둘 다 8로 동일하다.

    이 경우 어떠한 노드를 먼저 선택해도 상관이 없다. 위의 예에서는 노드 c를 먼저 선택했다고 가정하자.

    이제 V of A의 부분집합은 노드 a, 노드 b, 노드 c가 되었다.

(d) : 각 노드에 인접한 노드들을 탐색하여 그 중 가장 가중치가 작은 에지를 하나 선택하자. 이 경우, 가중치 2가 가장 작은 에지가 되었으므로 노드 i를 선택한다.

... 반복

(i) 이렇게 반복하다 보면 모든 노드들이 까맣게 칠해진다. 탐색이 끝났다.

 

 

 

• 왜 이렇게 하면 MST(Minimum Spanning Tree)가 찾아지는가?

- Prim 의 알고리즘의 임의의 한 단계를 생각해 보자.

- A를 현재까지 알고리즘이 선택한 에지의 집합이라고 하고, A를 포함하는 MST가 존재한다고 가정하자.

 

 

 

• 가중치가 최소인 에지 찾기

- V of A : 이미 트리에 포함된 노드들

- V of A에 아직 속하지 않은 각 노드 v에 대해서 다음과 같은 값을 유지

    - key(v) : 이미 V of A에 속한 노드와 자신을 연결하는 에지들 중 가중치가 최소인 에지 (u, v)의 가중치

    - π(v) : 그 에지 (u, v)의 끝점 u

 

MST-Prim (G, w, r)
	for each u∈V do
    	key[u] <-∞
        π[u] <- NIL
    end.
    V of A <- {r}
    key[r] <- 0
    while |V of A| < n do	// n-1번 반복
    	find u ∉ V of A with the minimum key value;	// 최소값 찾기 O(n)
        V of A <- V of A {u}
        for each V ∉ V of A adjacent to u do	// degree(u) = O(n)
        	if key[v] > w(u, v) then
            	key[v] <- w(u, v)
                π[v] <- u
            end.
        end.
    end.

 

* minimum key

• Key 값이 최소인 노드 찾기

- 최소 우선순위 큐를 사용

    - V-V of A에 속한 노드들을 저장

    - Extract-Min : key 값이 최소인 노드를 삭제하고 반환

 

 

MST-Prim (G, w, r)
	for each u∈V do
    	key[u] <-∞
        π[u] <- NIL
    key[r] <- 0
    Q <- V[G]
    while Q != 공집합
    	do u <- EXTRACT-MIN(Q)	// 최소값 찾기 O(logn)
        	for each v ∈ Adj[u]
            	do if v ∈ Q and w(u, v) < key[v]
                	then [v] <- u
                    	key[v] <- w(u, v)	// 우선순위 큐에서 key값 decrease : O(logn)

 

 

 

Prim의 알고리즘 : 시간복잡도

- 이진 힙(binary heap)을 사용하여 우선순위 큐를 구현한 경우

- while loop :

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

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

- 따라서 시간복잡도 : O(nlogn + mlogn) = O(mlogn)

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

- Fibonacci 힙을 사용하여 O(m+nlogn)에 구현 가능[Fredman-Tarjan 1984]