프림 알고리즘(prim algorithm)도 탐욕 알고리즘의 하나이며, 14장에서 다룰 데이크스트라 알고리즘과 매우 닮아 있습니다. 둘 모두 BFS와 유사합니다. 프림 알고리즘은 정점 하나를 가진 트리에서 시작하여 트리 내의 정점 v와 트리 밖의 정점 u를 잇는 에지 중에서 가중치가 가장 작은 에지 (u, v)를 트리의 에지로 만들고 정점 u도 트리에 포함시키며 트리를 확장해 나갑니다. 그러다가 트리의 정점 집합 V(T)=V(G)가 되면 알고리즘을 종료합니다. 그림으로 살펴보면 훨씬 나을 것입니다. 해당 부분을 설명할 때 하나씩 작동 과정을 따라가 보겠습니다. 그 전에 다음 절에서는 트리 안의 정점과 트리 밖을 잇는 에지 중에서 어떻게 가중치가 가장 작은 에지를 찾을 것인지 고민해 보겠습니다.