DataStructure - Prim 의 MST 알고리즘

• Prim 의 MST 알고리즘
  

Prim의 알고리즘은 하나의 정점에서부터 시작하여 트리를 단계적으로 확장해나가는 방법이다. 처음에는 시작 정점많이 트리에 포함된다. 다음으로 지금까지 만들어진 트리에 인접한 정점들 중에서 간선의 가중치가 가장 작은 정점을 선택하여 트리를 확장한다. 이 과정은 트리가 n-1ㅐ의 간선을 가질 때까지 계속된다.

Prim의 알고리즘을 자연어로 나타내면 알고리즘은 아래와 같다.

| Prim의 최소 비용 신장 트리 알고리즘

---

Prim( )

1. 그래프에서 시작 정점을 선택하여 초기 트리를 만든다.

2. 현재 트리의 정점들과 인접한 정점들 중에서 간선의 가중치가 가장 작은 정점   v 를 선택한다.

3. 이 정점 v와 이때의 간선을 트리에 추가한다.

4. 모든 정점이 삽입될 때 까지 2번으로 이동한다.

---

Kruskal의 알고리즘이 간선을 기반으로 하는 알고리즘인데 비해 Prim의 방법은 정점을 기반으로 한다.

Prim의 알고리즘은 주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복하므로 의 시간 복잡도를 가진다. Kruskal 의 알고리즘은 복잡도가 이므로 정점의 개수에 비해 간선의 개수가 매우 적은 희박한 그래프(sparse graph)를 대상으로 할 경우에는 Kruskal의 알고리즘이 적합하고, 반대로  간선이 매우 많은 그래프의 경우에는 Prim의 알고리즘이 유리하다고 볼 수 있다.