알고리즘 - 프림(Prim)

최소 신장 트리를 구하는 알고리즘.

 

1. 시작점을 아무거나 고른다.

2. 선택한 점을 최소 신장 트리에 추가한다.

3. 최소 신장 트리에 추가된 정점들과 일반그룹과 연결하는 간선중 가장 가중치가 낮은 간선을 추가.

4. 추가된 간선과 연결된 정점을 추가.

5. 3-4를 반복.

 

 

구현할 때는 최소값 우선순위 큐를 사용.

 

1. 시작 정점을 선택하고 그 점과 연결된 모든 간선을 우선순위 큐에 넣는다.

2. 시작점을 최소 신장 트리에 넣는다.

3. 우선순위 큐에는 최소 신장 트리에 포함된 정점과 그렇지 않은 정점들을 연결하는 간선이 모두 들어있음. 

4. 우선순위 큐에 들은 간선중 최소값 간선을 확인하고 연결된 정점이 최소신장트리에 들어있지 않다면 추가.

5. 최소 신장 트리가 완성될 때까지, 모든 정점이 최소 신장 트리에 포함될 때까지 작업을 반복