[자료구조] 프림 알고리즘

• 가중치가 있는 연결된 무방향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성 트리를 찾는 알고리즘
• 각 간선에 대한 정보를 우선순위 큐에 담아 처리하는 방식으로 구현

 

프림 알고리즘 작동 순서

1. 그래프에서 정점하나를 선택하여 트리 T에 포함시킴
2. T에 포함된 노드와 T에 포함되지 않은 노드 사이의 간선 중에서 가장 가중가 작은 간선을 찾음
3. 해당 간선에 연결된 T에 포함되지 않은 노드를 트리 T에 포함시킴
4. 모든 노드가 포함될 때까지 반복 각 간선에 대한 정보를 우선 순위 큐에 담아 처리하는 방식으로 구현

이미지 출처 : Quora - https://www.quora.com/What-is-the-best-explanation-for-Prims-and-Kruskals-algorithms

 

 

 

 

 

참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수