프림(Prim) 알고리즘은 가중치가 있는 무방향 그래프에서 최소 신장 트리(Minimum Spanning Tree, MST)를 찾는 대표적인 탐욕(Greedy) 알고리즘입니다. 그래프의 모든 정점을 포함하면서 간선 가중치의 합이 최소가 되는 트리를 구성하는 간선들의 부분 집합을 찾아냅니다.
이 알고리즘은 임의의 시작 정점에서 출발하여 한 번에 하나씩 정점을 트리에 추가해 나가는 방식으로 동작합니다. 매 단계마다 현재까지 만들어진 트리에서 다른 정점으로 이어지는 가장 저렴한 연결(간선)을 선택하는 것이 핵심입니다.
프림 알고리즘의 동작 원리
구체적인 예시를 통해 프림 알고리즘이 어떻게 작동하는지 단계별로 살펴보겠습니다.
1단계: 임의의 노드를 루트 노드로 선택
먼저 아무 노드나 골라 루트 노드로 지정합니다. 여기서는 S 노드를 프림 신장 트리의 루트로 선택했습니다.
"어떤 노드든 루트가 될 수 있는 이유는 무엇일까?"라고 궁금할 수 있습니다. 그 답은 간단합니다. 신장 트리에는 그래프의 모든 노드가 포함되어야 하며, 그래프가 연결되어 있다면 반드시 나머지 트리와 이어주는 간선이 하나 이상 존재하기 때문입니다.
2단계: 나가는 간선을 확인하고 비용이 가장 낮은 것을 선택
루트 노드 S를 선택한 후, S에서 뻗어 나가는 간선을 살펴봅니다. S-A 간선은 가중치가 7, S-C 간선은 8입니다. 더 작은 값을 가진 S-A 간선을 선택합니다.
이제 S-7-A 트리를 하나의 노드처럼 취급하고, 여기서 나가는 모든 간선을 확인합니다. 그중 비용이 가장 낮은 간선을 골라 트리에 추가합니다.
이 과정을 거쳐 S-7-A-3-C 트리가 완성됩니다. 다시 이 트리를 하나의 노드로 보고 모든 간선을 검사하되, 역시 최소 비용의 간선만 선택합니다. 이 경우 C-3-D가 새로운 간선이 되는데, 다른 간선들의 비용(8, 6, 4 등)보다 작기 때문입니다.
3단계: 동일한 비용의 간선 처리
노드 D를 신장 트리에 추가한 후, D에서 나가는 두 간선 D-2-T와 D-2-B의 비용이 같다는 것을 발견하게 됩니다. 이럴 때는 어느 쪽이든 먼저 추가할 수 있으며, 결과적으로 다음 단계에서도 비용 2인 간선이 최솟값이 되므로 결국 두 간선이 모두 포함된 신장 트리가 만들어집니다.
그럼 이제 이 알고리즘을 실제 코드로 구현하는 방법을 알아보겠습니다.
자바스크립트 구현 예제
primsMST() {
// MST를 담을 그래프 초기화
const MST = new Graph();
if (this.nodes.length === 0) {
return MST;
}
// 첫 번째 노드를 시작 노드로 선택
let s = this.nodes[0];
// 우선순위 큐(Priority Queue)와 탐색 완료 집합 생성
let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
let explored = new Set();
explored.add(s);
MST.addNode(s);
// 시작 노드의 모든 간선을 가중치를 우선순위로 하여 큐에 추가
this.edges[s].forEach(edge => {
edgeQueue.enqueue([s, edge.node], edge.weight);
});
// 가장 작은 간선을 꺼내 새 그래프에 추가
let currentMinEdge = edgeQueue.dequeue();
while (!edgeQueue.isEmpty()) {
// 아직 탐색하지 않은 노드를 향하는 간선을 찾을 때까지 제거
while (!edgeQueue.isEmpty() && explored.has(currentMinEdge.data[1])) {
currentMinEdge = edgeQueue.dequeue();
}
let nextNode = currentMinEdge.data[1];
// 큐가 빈 상태로 끝날 수 있으므로 한 번 더 확인
if (!explored.has(nextNode)) {
MST.addNode(nextNode);
MST.addEdge(currentMinEdge.data[0], nextNode, currentMinEdge.priority);
// 해당 노드의 모든 간선을 다시 우선순위 큐에 추가
this.edges[nextNode].forEach(edge => {
edgeQueue.enqueue([nextNode, edge.node], edge.weight);
});
// 이 노드를 탐색 완료로 표시
explored.add(nextNode);
s = nextNode;
}
}
return MST;
}테스트 코드
다음과 같이 그래프를 구성하고 프림 알고리즘을 실행해 볼 수 있습니다.
let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");
g.addEdge("A", "C", 100);
g.addEdge("A", "B", 3);
g.addEdge("A", "D", 4);
g.addEdge("C", "D", 3);
g.addEdge("D", "E", 8);
g.addEdge("E", "F", 10);
g.addEdge("B", "G", 9);
g.primsMST().display();실행 결과
위 코드를 실행하면 다음과 같은 출력이 나옵니다.
A->B, D B->A, G D->A, C, E C->D E->D, F G->B F->E
원본 그래프 구조
처음 입력된 그래프는 다음과 같은 구조입니다.
/** * A * / | \ * C | B * \ | | * D G * | / * E * | * F */
MST 적용 후 그래프 구조
프림 알고리즘을 적용한 후의 그래프는 다음과 같습니다.
/** * A * |\ * C | B * \ | | * D G * | * E * | * F * */
결과를 보면 가장 비용이 큰 간선들(A-C 간선의 가중치 100 등)이 제거되었고, 전체 정점을 모두 연결하면서 가중치 합이 최소가 되는 신장 트리가 완성된 것을 확인할 수 있습니다.
마무리
프림 알고리즘은 네트워크 설계, 도로/전력망 구축, 클러스터링 등 다양한 분야에서 활용되는 핵심 알고리즘입니다. 우선순위 큐를 활용하면 시간 복잡도를 O(E log V)까지 최적화할 수 있으므로, 실무에서는 효율적인 자료구조 선택이 중요합니다.