프림(Prim) 알고리즘이란?
모든 정점이 연결된 그래프 G(V, E)가 주어지고, 각 간선에는 가중치(비용)가 부여되어 있다고 가정합니다. 프림(Prim) 알고리즘은 이 그래프에서 최소 신장 트리(Minimum Spanning Tree, MST), 즉 모든 정점을 연결하면서 간선 가중치의 합이 최소가 되는 트리를 찾아내는 대표적인 탐욕(Greedy) 기반 알고리즘입니다.
프림 알고리즘은 성장 트리(growing tree) 방식으로 동작합니다. 하나의 시작 정점(시드, seed)에서 트리를 시작한 뒤, 가중치가 가장 작은 간선을 하나씩 추가하며 트리를 점차 확장해 전체 그래프를 덮을 때까지 반복합니다.
문제는 두 개의 집합(set)을 이용해 해결합니다. 하나는 이미 선택된 노드를 보관하는 집합이고, 다른 하나는 아직 고려하지 않은 노드를 보관하는 집합입니다. 시작 정점에서 출발해 인접 정점 중 간선 비용이 최소인 정점을 선택하는 방식으로, 노드를 하나씩 트리에 추가하며 성장시켜 나갑니다.
이 알고리즘의 시간 복잡도는 O(V²)입니다. 여기서 V는 정점(vertex)의 개수를 의미합니다.
입력 및 출력 예시
입력 − 그래프의 인접 행렬(adjacency matrix) −
출력 −
(0)---(1|1) (0)---(2|3) (0)---(3|4) (1)---(0|1) (1)---(4|2) (2)---(0|3) (3)---(0|4) (4)---(1|2) (4)---(5|2) (5)---(4|2) (5)---(6|3) (6)---(5|3)
위 출력에서 각 항목은 "(정점)---(정점|간선 비용)" 형태로, MST에 포함된 간선과 그 비용을 나타냅니다. 이 예제에서 선택된 간선의 비용은 1 + 3 + 4 + 2 + 2 + 3이므로 총 비용은 15입니다.
알고리즘 (의사코드)
prims(g: Graph, t: tree, start)
입력 − 그래프 g, 빈 트리 t, 시작 정점 'start'
출력 − 간선이 추가된 완성된 트리
Begin
define two sets as usedVert, unusedVert
usedVert[0] := start and unusedVert[0] := φ
for all vertices except start do
usedVert[i] := φ;
unusedVert[i] := i //add all vertices in unused list
done
while number of vertices in usedVert ≠ V do //V is number of total nodes
min := ∞;
for all vertices of usedVert array do
for all vertices of the graph do
if min > cost[i,j] AND i ≠ j then
min := cost[i,j]
ed := edge between i and j, and cost of ed := min
done
done
unusedVert[destination of ed] := φ;
add edge ed into the tree t
add source of ed into usedVert
done
End
동작 과정 요약
- 사용한 정점 집합(usedVert)과 아직 사용하지 않은 정점 집합(unusedVert)을 초기화합니다.
- 사용한 정점의 수가 전체 정점 수 V와 같아질 때까지 반복합니다.
- 현재 트리에 속한 정점과 그렇지 않은 정점을 잇는 간선 중 비용이 최소인 간선을 찾습니다.
- 해당 간선을 트리에 추가하고, 도착 정점은 unusedVert에서 제거한 뒤 시작 정점을 usedVert에 추가합니다.
C++ 구현 예제
#include<iostream>
#define V 7
#define INF 999
using namespace std;
//그래프의 비용 행렬(cost matrix)
int costMat[V][V] = {
{0, 1, 3, 4, INF, 5, INF},
{1, 0, INF, 7, 2, INF, INF},
{3, INF, 0, INF, 8, INF, INF},
{4, 7, INF, 0, INF, INF, INF},
{INF, 2, 8, INF, 0, 2, 4},
{5, INF, INF, INF, 2, 0, 3},
{INF, INF, INF, INF, 4, 3, 0}
};
typedef struct{
int u, v, cost;
}edge;
class Tree{
int n;
edge edges[V-1]; //트리는 (정점 수 - 1)개의 간선을 가짐
public:
Tree(){
n = 0;
}
void addEdge(edge e){
edges[n] = e; //트리에 간선 e 추가
n++;
}
void printEdges(){ //간선, 비용, 총 비용 출력
int tCost = 0;
for(int i = 0; i<n; i++){
cout << "Edge: " << char(edges[i].u+'A') << "--" << char(edges[i].v+'A');
cout << " And Cost: " << edges[i].cost << endl;
tCost += edges[i].cost;
}
cout << "Total Cost: " << tCost << endl;
}
friend void prims(Tree &tre, int start);
};
void prims(Tree &tr, int start){
int usedVert[V], unusedVert[V];
int i, j, min, p;
edge ed;
//초기화
usedVert[0] = start; p = 1;
unusedVert[0] = -1;//-1은 해당 위치가 비어 있음을 의미
for(i = 1; i<V; i++){
usedVert[i] = -1;//첫 번째 위치를 제외한 모든 곳은 비워 둠
unusedVert[i] = i;//정점들로 채움
}
tr.n = 0;
//간선을 구해 트리에 추가
while(p != V){ //p는 usedVert 배열에 있는 정점의 수
min = INF;
for(i = 0; i<p; i++){
for(j = 0; j<V; j++){
if(unusedVert[j] != -1){
if(min > costMat[i][j] && costMat[i][j] != 0){
//u는 이미 고려되었고 v는 아직 고려되지 않은
//상태에서 최소 비용 간선을 찾음
min = costMat[i][j];
ed.u = i; ed.v = j; ed.cost = min;
}
}
}
}
unusedVert[ed.v] = -1;//v를 unusedVertex에서 삭제
tr.addEdge(ed);
usedVert[p] = ed.u; p++;//u를 usedVertex에 추가
}
}
int main(){
Tree tr;
prims(tr, 0); //시작 노드 0
tr.printEdges();
}
실행 결과
(0)---(1|1) (0)---(2|3) (0)---(3|4) (1)---(0|1) (1)---(4|2) (2)---(0|3) (3)---(0|4) (4)---(1|2) (4)---(5|2) (5)---(4|2) (5)---(6|3) (6)---(5|3)
프로그램은 정점 0(A)에서 시작해 MST를 구성하는 간선들을 순서대로 출력하고, 마지막에 총 비용(Total Cost: 15)까지 함께 보여줍니다. 이처럼 프림 알고리즘은 매 단계에서 최소 비용 간선을 선택하는 탐욕적 선택이 전체 최적해로 이어진다는 점을 활용해 효율적으로 최소 신장 트리를 구할 수 있습니다.