프림(Prim) 최소 신장 트리(MST) 알고리즘 완벽 정리

프림 알고리즘이란?

모든 간선에 가중치(비용)가 부여된 연결 그래프 G(V, E)가 주어졌을 때, 프림(Prim) 알고리즘은 이 그래프에서 최소 신장 트리(Minimum Spanning Tree, MST)를 찾는 대표적인 탐욕(Greedy) 기반 알고리즘입니다.

프림 알고리즘은 성장하는 트리(Growing Tree) 방식으로 동작합니다. 시작을 위해 하나의 시드(seed) 정점이 필요하며, 이 시드 정점에서 출발해 간선을 하나씩 추가하면서 전체 트리를 점진적으로 확장해 나갑니다.

동작 원리

프림 알고리즘은 두 개의 집합(set)을 사용해 문제를 해결합니다.

• 사용된 정점 집합(usedVert): 이미 트리에 포함된 노드들을 저장
• 미사용 정점 집합(unusedVert): 아직 고려되지 않은 노드들을 저장

시드 정점에서 시작하여, 사용된 정점들에 연결된 간선 중 비용이 최소인 간선을 선택하고 해당 정점을 트리에 추가합니다. 이 과정을 반복하며 노드를 하나씩 트리에 편입시켜 트리를 성장시킵니다.

이 알고리즘의 시간 복잡도는 O(V²)입니다. 여기서 V는 정점(vertex)의 개수입니다.

입력과 출력

입력:
그래프의 인접 리스트:

출력:
(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)

알고리즘 의사코드

prims(g: Graph, t: tree, start)

입력 − 그래프 g, 빈 트리 t, 시드 정점 'start'

출력 − 간선이 추가된 완성된 트리

Begin
    usedVert, unusedVert 두 개의 집합을 정의
    usedVert[0] := start, unusedVert[0] := φ

    start를 제외한 모든 정점에 대해
        usedVert[i] := φ
        unusedVert[i] := i   // 미사용 목록에 모든 정점 추가
    done

    while usedVert의 정점 수 ≠ V do   // V는 전체 노드 수
        min := ∞
        for usedVert 배열의 모든 정점 do
            for 그래프의 모든 정점 do
                if min > cost[i,j] AND i ≠ j then
                    min := cost[i,j]
                    ed := i와 j 사이의 간선, ed의 비용 := min
            done
        done

        unusedVert[ed의 도착 정점] := φ
        간선 ed를 트리 t에 추가
        ed의 출발 정점을 usedVert에 추가
    done
End

C++ 구현 예제

#include<iostream>
#define V 7
#define INF 999
using namespace std;

// 그래프의 비용 행렬
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;     // unusedVertex에서 v 제거
        tr.addEdge(ed);
        usedVert[p] = ed.u; p++;   // u를 usedVertex에 추가
    }
}

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)

정리

프림 알고리즘은 하나의 시작 정점에서 출발해 매 단계마다 트리에 연결된 간선 중 가장 작은 가중치의 간선을 선택하는 탐욕적 방법입니다. 크루스칼(Kruskal) 알고리즘이 간선 중심으로 동작하는 것과 달리, 프림 알고리즘은 정점 중심으로 트리를 확장한다는 특징이 있습니다. 밀집 그래프(dense graph)에서 특히 유용하며, 우선순위 큐와 인접 리스트를 활용하면 시간 복잡도를 O(E log V)까지 개선할 수 있습니다.