[알고리즘] MST(3) - 프림 알고리즘 ( Prim's Algorithm )

이번에는 MST의 두 번째 알고리즘 Prim's 알고리즘에 대해 알아보겠습니다.

BFS를 기억하시나요? ( 링크 )

Prim's 알고리즘은 BFS와 같이 시작점을 기준으로 간선이 확장해나가는 방식입니다.

대신 Prim's 알고리즘은 간선에 가중치가 있으며, 최소한의 비용을 갖는 트리를 만들어야 한다는 점에서 차이가 있습니다.

Prim's 알고리즘에서는 특별히 사전에 알아둬야 할 내용이 없으므로 바로 어떻게 동작하는지 알아보도록 하겠습니다.

1. Prim's 알고리즘

Prim's 알고리즘은 최소 우선순위 큐에서 가중치가 가장 작은 정점을 선택한 후,

그 정점의 인접한 정점들에 대해 key 값과 연결된 가중치 값을 비교하여 key값을 갱신할 지 말지 결정합니다.

초기 그래프입니다.

모든 정점들의 key 값은 inf가 할당되어 있습니다.

그 이유는 Prim's 알고리즘이 최소 우선 순위 큐에서 각 정점의 key값들 중

최소 값을 뽑아 그 정점을 이용하여 다음 단계를 진행하게 되기 때문입니다.

그래서 어떠한 가중치보다 큰 값으로 설정하기 위해 inf를 할당합니다.

start vertex를 설정합니다.

Prim's 알고리즘은 어떤 vertex를 start로 하든 항상 같은 트리가 형성됩니다.

start vertex는 초기 값으로 key값을 0으로 할당합니다.

Step 2에서 큐에는 { 0, inf , inf , inf , inf , inf , inf } 원소들이 있고,

그 중에서 0이 가장 작으므로 start vertex가 선택됩니다.

선택된 vertex에 대해서 인접 간선의 가중치와 정점의 key 값을 확인합니다.

즉 Step 4 ~ Step 7은 하나의 큰 단계라고 보시면 됩니다.

수도 코드에서는 이를 반복문으로 표현하고 있습니다.

첫 번째로 가중치가 9인 간선을 확인합니다.

Step 3에서 start vertex와 가중치가 9인 간선으로 연결된 정점의 key 값은 inf였습니다.

즉 가중치 = 9  ,  key 값 = inf

9 < inf 이므로 정점의 key 값을 가중치의 값으로 바꿔줍니다.

이것이 Prim's 알고리즘이 MST를 만드는 규칙입니다.

그리고 key 값이 변경된 정점의 부모는 start vertex라는 것을 표현하기 위해 화살표로 표시하겠습니다.

다음으로 가중치가 6인 간선에 대해, Step 4의 과정을 수행합니다.

Step 4에서 가중치 값 = 6  <  inf = key 값

이므로 key 값을 6으로 변경합니다.

이전 단계와 같습니다.

이전 단계와 같습니다.

이제 start vertex에 대해서 모든 간선들을 확인해보았습니다.

그러면 이제 다음 정점을 선택하기 위해 최소 우선 순위 큐에서 key 값이 가장 작은 정점을 고릅니다.

지금 우선 순위 큐에는 { 5 , 7 , inf , 6 , inf , 9 } 가 있으므로 가장작은 값은 5입니다.

Step 9부터는 key 값이 5인 정점에 대해 Step 4 ~ Step 7의 과정을 수행할 것입니다.

key 값이 5인 정점과 연결된 간선들 보니 가중치가 10인 간선이 있고,

이 간선과 연결된 정점의 key 값은 7입니다.

가중치 = 10   >  7 = key 값

이므로 key 값을 변경하지 않습니다.

key 값을 변경하는 것은 가중치보다 key 값이 더 클 경우에만 해당됩니다.

연결된 간선이 1개 밖에 없으므로 다시 최소 우선순위 큐에서 또 정점을 골라야겠네요.

다음에 선택된 정점은 key 값이 6 정점입니다.

인접한 간선들의 가중치는 12 , 11 , 15 이네요.

Step 10에서 가중치가 15인 간선에 대해, 이 간선과 연결된 정점의 key 값은 inf이므로

가중치 = 15  <  inf = key 값

따라서 key 값을 변경합니다.

이전 단계와 같습니다.

가중치 = 12  <  7 = key 값

이므로 key 값을 변경하지 않습니다.

우선순위 큐 중에서 값이 가장작은 정점이 선택됩니다.

연결된 간선 중 가중치가 2인 간선에 대해, 연결된 정점의 key 값은 11입니다.

가중치 = 2  <  11 = key 값

이므로 key 값을 변경합니다.

이 때 key 값이 변경되는 정점은 이미 가중치가 11인 간선을 갖고 있었습니다.

그런데 key 값이 새로 변경되었으므로 부모를 갱신해야 합니다.

이제 더 특별한 것은 없으므로 이후의 과정은 생략하도록 하겠습니다.

그림이 20장이 되네요...

Prim's 알고리즘은 최소 우선순위 큐에서 key 값이 작은 정점을 고른 후(extract : 추출)  그 정점의 인접한 간선의 가중치와 연결된 정점의 key 값을 비교해서 연결된 정점의 key 값을 갱신할지 말지를 결정하는 것을 통해 MST를 구현합니다.

실제로 결과를 보면 화살표로 연결된 가중치의 합이 다른 어떤 트리보다 최소가 된다는 것을 확인할 수 있습니다.

2. 수도코드

1) line 1 ~ 3

그래프의 모든 정점에 대해 key 값을 inf로 할당하고, 부모를 NIL로 할당합니다.

2) line 4 ~ 5

시작 정점의 key 값을 0으로 하고, 그래프의 모든 점을 최소 우선순위 큐에 삽입합니다.

3) line 6 ~ 7

최소 우선순위 큐가 비어있을 때까지 반복문을 수행하며, 매 반복문 마다 key 값이 최소인 정점을 추출합니다.

4) line 8 ~ 11

추출한 정점의 모든 인접한 정점에 대해,

가중치와 정점의 key 값을 비교해서 key 값이 더 크면 key 값을 가중치 값으로 변경하고, 부모를 추출된 정점에 할당합니다.

5) 시간 복잡도

Prim's 알고리즘의 시간 복잡도는 최소 우선순위 큐를 어떻게 구현하느냐에 따라 다릅니다.

대표적으로 binary heap , unsorted array으로 구현할 수 있으며

결론부터 말씀드리면 binary heap은 이고, unsorted array는 입니다.

일반화된 시간 복잡도 식은 다음과 같습니다.

즉 ( 정점의 개수 * extract-min의 수행시간 ) + ( 간선의 개수 * key 값을 변경하는데 걸리는 시간 ) 으로 계산됩니다.

왜냐하면 정점의 개수만큼 최소 우선순위 큐에서 extract를 하고, 인접한 간선의 개수만큼 key값을 변경하는 작업이 이루어지기 때문이죠.

case1) binary heap의 경우

while 내부는 번 수행되고, extract-min은  시간이 걸리므로 

그리고 8~11행의 for 문은 번 수행되고, decrease-key는 시간이 걸리므로 

case2) unsorted array의 경우

이고,  

이상으로 Prim's 알고리즘에 대해 알아보았습니다.

Prim's 알고리즘은 최소 우선순위 큐에서 key 값이 작은 정점을 추출(extract -min) 한 후 그 정점의 인접한 간선의 가중치와 연결된 정점의 key 값을 비교해서 연결된 정점의 key 값을 갱신할지 말지를 결정(Decrease - key)하는 것을 통해 MST를 구현합니다.