프림(Prim) 알고리즘이란? 최소신장트리(MST, Minimum Spanning Tree) 를 찾기 위한 대표적인 알고리즘입니다. 여기에서 최소신장트리란, 아래와 같이 모든 노드를 연결하는 부분 그래프 중, 가장 비용이 적은 것입니다. 하늘색으로 표시한 경로가 최소신장트리입니다. 여기에서 최소신장트리의 길이는 (4 + 8 + 16 + 20) = 48 이 되겠습니다. 최소신장트리를 찾는 알고리즘은 크루스칼(Kruskal) 과 프림(Prim) 이 대표적입니다. 오늘은 그 중에서도 프림 알고리즘에 대해서 알아보겠습니다. 동작원리 프림 알고리즘에서는 MST의 후보가 될 간선을 담을 우선순위 큐가 필요합니다. 우선순위 큐는 최소의 비용을 가지는 경로가 우선순위를 갖게 합니다. (보통 Min Heap을 이용해서 ..