prim 알고리즘

*프림 알고리즘

 

- 최소 신장 트리 알고리즘(MST)

- 그래프에서 최단 경로를 찾는 다익스트라의 알고리즘과 흡사하게 동작

- 집합 A의 간선이 항상 하나의 트리를 이룸

- 트리는 임의의 루트로부터 시작해 그래프의 모든 정점을 모두 포함할때까지 확장

- 알고리즘이 종료될때 A의 간선은 최소 신장 트리를 이룸

- 매 단계마다 추가 가능한 간선중 가장 적은 가중치를 가진 간선을 더해 트리를 확장하기 때문에 Greedy 한 알고리즘이 된다.