최소비용신장트리 - 4

prim의 알고리즘

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

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

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

MST가 되는 이유

- S 와 V-S에서 cross를하면서 가장 가벼운 노드를 고르는 것이므로 MST가 될수 있다.

 

가중치가 최소인 에지 찾기

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

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

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

- 노드들 중에서 key값이 최소인 값을 찾으면 된다.

- 다음 노드를 찾는데 걸리는 시간이 줄어든다 -> 시간복잡도 o(n)

** 아직 key값을 계산해야함

- 최소인 f값을 찾아서 연결하고

- f와 연결된 노드들의 key값을 수정하면 된다 -> 빨간부분과 연결된 가중치보다 f와 연결된 가중치가 더 작을때 바꿔주면 된다.

prim 알고리즘 수도코드

key값이 최소인 원소 찾기

- 최소 우선순위 큐를 사용

• V-Va에 속한 노드들을 저장
• Extract-Min : key값이 최소인 노드를 삭제하고 반환

 Prim의 알고리즘 시간복잡도

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

- while loop :

• n번의 Extract-Min 연산 : o(logn)
• m번의 Decrease-key 연산 : o(mlogn)

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

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

- Fibonacci 힙을 사용하여 o(m+nlogn)에 구현 가능

 

** 위의 그림들은 '영리한 프로그래밍을 위한 알고리즘 강좌'에서 가져왔습니다.