(4)최소 비용 신장 트리(MST) Prim 알고리즘

Prim의 알고리즘

1. 임의의 노드를 출발 노드로 선택한다. 
2. 출발 노드를 포함하는 트리를 점점 키워감
3. 매 단계에서 이미 트리에서 포함된 노드와 포함되지 않은 노드를 연결하는 에지들 중 가장 가중치가 작은 에지를 선택한다. 

실제 실행 순서

실행 해보면 누가 봐도 특별한 어려움이 없을 것이다. 크루스칼이나 프림이나 이론은 별로 어려운 것이 없는 것 같다. 언제나 그렇듯 실제 구현이 문제이다. 

가중치가 최소인 엣지 찾기에 대해 논해보겠다.

key는 엣지가 가장 작은 정점 파이는 가장 작은 가중치의 도착점이다. 예를 들면 아래와 같다. 

가중치가 최소인 엣지를 찾기 보단 key값이 최소인 엣지를 찾는 것이 중요하다. 

key값이 최소인 엣지를 찾는 것은 적어도 n개 보다 작은 수의 엣지를 봐야함으로 O(n)이 걸린다. 최소 엣지를 구할 때 (n^2)이 걸리는 것에 비해 많이 빨라졌다. 

만약 프림 알고리즘에서 새로운 노드 f가 추가되면 f와 인접한 노드들 중 더 작은 가중치가 있다면 갱신해줍니다. e는 key값이 10이되고 g는 key값이 2가됩니다. 파이는 f로 갱신됩니다. 

갱신해주는 것도 O(n)이 걸립니다. 왜냐하면 n보다 적은 수의 정점에 방문하여 O(n)이 됩니다. 

 

-> O(n^2)이다. 만약 최소 가중치를 골랐더라면 O(n^3)이 걸렸을 것이다. 

만약 배열을 사용하여 구현해주었다면 최소 값을 찾는데 O(n^2)이 걸렸다면 우선순위 큐를 사용하여 구현하게 될 경우에는 O(mlogn)이 될 것이다.