C++로 배우는 프림(Prim) 알고리즘: 인접 행렬 기반 간단 구현

프림(Prim) 알고리즘 개요

프림(Prim) 알고리즘은 주어진 가중치 무방향 그래프에서 최소 신장 트리(Minimum Spanning Tree, MST)를 찾기 위해 사용되는 대표적인 그리디(Greedy) 기반 알고리즘입니다. 하나의 시작 정점에서 출발하여, 트리에 속한 정점과 속하지 않은 정점을 잇는 간선 중 가장 가중치가 낮은 것을 반복적으로 추가하며 트리를 확장해 나갑니다.

핵심 용어 정리

가중치 그래프(Weighted Graph) — 모든 간선에 가중치(비용) 값이 부여된 그래프입니다.

무방향 그래프(Undirected Graph) — 모든 간선이 양방향으로 연결되어 있는 특수한 형태의 그래프입니다.

최소 신장 트리(MST) — 그래프의 모든 정점을 포함하면서 사이클이 없고, 간선 가중치의 합이 가능한 한 가장 작아지는 간선들의 부분 집합입니다.

일반적으로 프림 알고리즘은 두 개의 배열을 사용하지만, 이 글에서는 단 하나의 불리언 배열(inMST)만 사용하여 더 단순하고 직관적인 구현 방법을 소개합니다.

C++ 구현 코드

아래 예제는 5개의 정점을 가진 그래프를 인접 행렬로 표현하고, 프림 알고리즘을 적용해 최소 신장 트리를 구성하는 프로그램입니다. 행렬에서 INT_MAX는 두 정점 사이에 직접 연결된 간선이 없음을 의미합니다.

#include <bits/stdc++.h>
using namespace std;
#define V 5
bool createsMST(int u, int v, vector<bool> inMST){
    if (u == v)
        return false;
    if (inMST[u] == false && inMST[v] == false)
        return false;
    else if (inMST[u] == true && inMST[v] == true)
        return false;
    return true;
}
void printMinSpanningTree(int cost[][V]){
    vector<bool> inMST(V, false);
    inMST[0] = true;
    int edgeNo = 0, MSTcost = 0;
    while (edgeNo < V - 1) {
        int min = INT_MAX, a = -1, b = -1;
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (cost[i][j] < min) {
                    if (createsMST(i, j, inMST)) {
                        min = cost[i][j];
                        a = i;
                        b = j;
                    }
                }
            }
        }
        if (a != -1 && b != -1) {
            cout<<"Edge "<<edgeNo++<<" : ("<<a<<" , "<<b<<" ) : cost = "<<min<<endl;
            MSTcost += min;
            inMST[b] = inMST[a] = true;
        }
    }
    cout<<"Cost of Minimum spanning tree ="<<MSTcost;
}
int main() {
    int cost[][V] = {
        { INT_MAX, 12, INT_MAX, 25, INT_MAX },
        { 12, INT_MAX, 11, 8, 12 },
        { INT_MAX, 11, INT_MAX, INT_MAX, 17 },
        { 25, 8, INT_MAX, INT_MAX, 15 },
        { INT_MAX, 12, 17, 15, INT_MAX },
    };
    cout<<"The Minimum spanning tree for the given tree is :\n";
    printMinSpanningTree(cost);
    return 0;
}

실행 결과

The Minimum spanning tree for the given tree is :
Edge 0 : (0 , 1 ) : cost = 12
Edge 1 : (1 , 3 ) : cost = 8
Edge 2 : (1 , 2 ) : cost = 11
Edge 3 : (1 , 4 ) : cost = 12
Cost of Minimum spanning tree =43

코드 동작 원리

createsMST() 함수는 간선 (u, v)를 MST에 추가할 수 있는지 검사합니다. 두 정점이 모두 MST에 이미 포함되어 있으면 사이클이 발생하므로 false를, 둘 다 포함되어 있지 않으면 그래프가 분리되므로 역시 false를 반환합니다. 오직 한쪽 정점만 MST에 속한 경우에만 true를 반환합니다.

printMinSpanningTree() 함수는 정점 0에서 시작하여, MST에 포함된 정점과 포함되지 않은 정점을 연결하는 간선 중 가중치가 가장 작은 것을 매 단계마다 선택합니다. 선택된 간선의 번호, 양 끝 정점, 비용을 출력하고 총비용에 더한 뒤, 해당 정점들을 MST에 포함시킵니다. 이 과정은 간선 개수가 V−1개가 될 때까지 반복됩니다.

이 구현은 매 단계마다 V×V 크기의 인접 행렬 전체를 스캔하므로 시간 복잡도는 O(V³)입니다. 우선순위 큐와 인접 리스트를 함께 사용하면 O(E log V)까지 최적화할 수 있으므로, 정점과 간선의 수가 많은 그래프에서는 최적화된 버전을 사용하는 것이 좋습니다.