[ 알고리즘 개념 ] 프림 알고리즘 (Prim Algorithm)

프림 알고리즘 (Prim Algorithm)

최소 신장 트리 (Minimum Spanning Tree)

 

1. 개념

크루스칼 알고리즘과 마찬가지로 대표적인 최소 신장 트리 알고리즘으로써, 그리디 알고리즘으로 최적해를 보장하는 드문  사례이다. 

최소 신장 트리에 대한 개념은 아래 글에 정리해두었다.https://codingexplore.tistory.com/61

[ 알고리즘 개념 ] 최소신장트리 (Minimum Spanning Tree)

 

2. 동작 과정

1) 임의의 간선 선택

2) 선택한 간선으로부터 가장 가중치가 낮은 간선을 선택 (이때, 사이클을 형성해선 안된다)

3) 모든 정점이 연결될 때까지 2번 과정 반복

 

3. 동작 예

프림 알고리즘 예

 

관련글

크루스칼 알고리즘

https://codingexplore.tistory.com/62

[ 알고리즘 개념 ] 크루스칼 알고리즘 (Kruskal Algorithm)

---

참고자료

https://www.skedsoft.com/books/design-analysis-of-algorithm/the-algorithms-of-kruskal-and-prim

The Algorithms Of Kruskal And Prim