Prim's Algorithm은 먼저 다루었던 크루스칼 알고리즘과 같은 대표적인 최소 신장 트리 알고리즘이다. 프림 알고리즘이 크루스칼 알고리즘보다 조금 더 복잡하다. 두 알고리즘 모두 탐욕 알고리즘을 기반으로 하는데, Kruskal's algorithm은 단순히 가중치를 기준으로 sorting하여 작은 것부터 선택하며 MST를 구하지만, Prim's algorithm은 특정 정점에서 시작하여, 이 정점에 연결된 가장 작은 가중치의 간선을 선택하며 MST를 구한다. 하나의 정점을 정하고, 이 정점에 연결되어 있는 간선들을 리스트에 담은 후, 이 리스트에서 weight가 가장 작은 간선을 선택하여 cycle이 이루어지지 않는지 확인하고 연결한다. 이 때 간선들을 담는 리스트의 자료형으로 최소힙을 사용하면 ..
