Prim Algorithm

Prim 알고리즘

 대표적인 최소신장트리 알고리즘 ex) Prim, Kruskal 알고리즘

• 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장하는 방법
• 정점 선택을 기반으로 하는 알고리즘
• 이전 단계에서 만들어진 신장 트리를 확장하는 방법   

시작 정점을 선택한 후, 정점에 인접한 간선 중 최소 가중치로 연결된 정점을 선택.

해당 정점에서 다시 최소 가중치로 연결된 정점을 선택.

=> 그리디 알고리즘

 

 

 

• Prim 알고리즘 예

출처 : https://gmlwjd9405.github.io/2018/08/30/algorithm-prim-mst.html

 

1. 임의의 정점을 선택. 연결된 노드 집합에 삽입.
2. 현재 정점에 연결된 간선들을 간선 리스트에 삽입
3. 간선 리스트에서 최소가중치를 가지는 간선 추출
4. 추출한 간선은 간선 리스트에서 삭제
5. 간선 리스트에 더 이상 간선이 없을 때 까지 3,4번 반복

3번 과정에서,

    if 해당 간선에 연결된 정점이 연결된 노드 집합에 이미 들어있다면:

        스킵 (사이클 x)

    else:

        해당 간선 선택. 해당 간선 정보를 최소 신장 트리에 삽입

 

 

 

• Prim 알고리즘 시간 복잡도

메인 반복문이 정점의 수 n만큼 반복.

내부반복문도 n번 반복.

  => O(n^2) (in 행렬)

  => O(m log n) (in 최소힙) (n: 정점 수, m: 간선 수)

 

간선이 많은 그래프, 밀집 그래프(Dense Graph)에 적합

 

 

 

 

 

참고: https://devlog-wjdrbs96.tistory.com/101

https://gmlwjd9405.github.io/2018/08/30/algorithm-prim-mst.html