프림의 최소 스패닝 트리 알고리즘_1

크루스칼 알고리즘

• 가장 작은 가중치부터 큰 가중치까지 순서대로 간선의 연결 상태를 보지 않고 나열 후
  싸이클 여부만을 확인하면서 추가
• 전체 간선에 대해서 최소값부터

프림 알고리즘

• 특정 시작 노드에 연결된 간선들을 확인 후 그 중 가장 작은 가중치의 간선에 대해서 싸이클 여부를 확인하면서 추가
• 인접 간선에 대해서 최소값 부터

두 알고리즘의 공통점

• 탐욕 알고리즘을 기초로 하고 있다

프림 알고리즘

순서도

1. 임의의 정점을 선택, '연결된 노드 집합'에 넣는다
2. 선택된 정점에 연결된 간선들을 간선 리스트에 넣는다
3. 간선 리스트에서 최소 가중치를 가지는 간선부터 추출
   • 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어있다면 skip (싸이클 방지)
   • 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 들어있지 않다면, 해당 간선을 선택 후 최소 신장 트리에 넣는다
4. 추출한 간선은 간선 리스트에서 제거한다
5. 간선 리스트에 더이상 간선 리스트가 없을때 까지 구간 2~4를 반복시행한다