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

프림 알고리즘(Prim's algorithm)은 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성나무를 찾는 알고리즘이다. 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 이진 힙을 이용하여 자료를 처리하였을 때를 기준으로 O(ElogV)의 시간복잡도를 가진다. 자세한 내용은 여기를 클릭! (출처 : 위키백과) 개요 프림 알고리즘은 아래의 순서대로 작동한다: 그래프에서 하나의 꼭짓점을 선택하여 트리를 만든다. 그래프의 모든 변이 들어 있는 집합을 만든다. 모든 꼭짓점이 트리에 포함되어 있지 않은 동안 트리와 연결된 변 가운데 트리 속의 두 꼭짓점을 연결하지 않는 가장 가중치가 작은 변을 트리에 추가한다. 알..