Prim(프림)의 알고리즘

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다.

Prim(프림)의 알고리즘

가중치가 있는 연결된 무향 그래프의 모든 꼭지점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성나무를 찾는 알고리즘이다.

변의 개수를 E, 꼭지점의 개수를 V라고 하면 이 알고리즘은 이진 힙을 이용하여 자료를 처리하였을 때를 기준으로 의 시간복잡도를 가진다.

프림의 알고리즘은 아래의 순서대로 작동한다.

1. 그래프에서 하나의 꼭지점을 선택하여 트리를 만든다.

2. 그래프의 모든 변이 들어 있는 집합을 만든다.

3. 모든 꼭지점이 트리에 포함되어 있지 않은 동안

1) 트리와 연결된 변 가운데 트리 속의 두 꼭지점을 연결하지 않는 가장 가중치가 작은 변을 트리에 추가한다.

알고리즘이 종료되었을 때 만들어진 트리는 최소 비용 신장트리가 된다.

출처 : 위키백과

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

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

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

왜 MST가 찾아지는가?

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

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

- 출발노드에 이미 연결된 노드와 그렇지 않은 노드를 연결하는 에지들 중 lighest edge.

가중치가 최소인 에지 찾기

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

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

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

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

가중치가 최소인 에지를 찾는 대신 key값이 최소인 노드를 찾는다.

-> key 값이 최소인 노드 f를 찾고 에지(f, π(f))를 선택한다.

-> 노드 d, g, e,의 key 값과 π값을 갱신한다.

의사코드

MST-Prim(G, w, r){
	for each u∈V do
		key[u] <- ∞
		π[u] <- NIL
	end.
	Va <- {r}
	key[r] <- 0
	while |Va| < n do
		find u!∈Va with the minimum key value;
		Va <- Va∪{u}
		for each v!∈Va adjacent to u do
			if key[v] > w(u, v) then
				key[v] <- w(u, v)
				π[v] <- u
			end.
		end.
	end.
}

key 값이 최소인 노드 찾기

- 최소 우선순위 큐를 사용

- V-Va에 속한 노드들을 저장

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

MST-PRIM(G, w, r){
	for each u∈V[G]
		do key[u] <- ∞
			π[u] <- NIL
	key[r] <- 0
	Q <- V[G]
	while Q != 0
		do u <- EXTRACT-MIN(Q) // EXTRACT-MIN(Q) : 최소값 찾기
			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)
}

시간복잡도

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

- while loop : 

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

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

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

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

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

소스 코드(Java)