프림 알고리즘 (Prim) — MST를 찾는 그리디 전략

“지금까지 만든 트리에 가장 싸게 연결할 수 있는 정점을 다음으로 붙인다.” 프림은 이 한 줄을 끝까지 반복하는 그리디 알고리즘이다. 답은 MST에서 보았듯이 정확히 $n - 1$개의 간선으로 이루어진 트리다.

알고리즘의 아이디어

Prim은 가중 무방향 연결 그래프 $G = (V, E, w)$에서 MST를 찾는 알고리즘이다. 이 전제(가중치가 붙은, 방향 없는, 연결된 그래프) 위에서 다음과 같이 동작한다.

1. 임의의 한 정점에서 시작한다. 그 정점 하나만으로 된 트리가 초기 상태다.
2. 현재 트리의 정점 집합 $V_T$와 바깥 정점 집합 $V \setminus V_T$를 가르는 컷(cut)을 가로지르는 간선(한 끝은 트리 안, 다른 끝은 트리 밖) 중 가장 작은 가중치의 간선을 선택해 트리에 추가한다.
   • 이렇게 컷을 가로지르는 간선만 후보로 삼으면, 양 끝점이 모두 트리 안에 있는 간선은 자연히 제외되어 사이클이 생기지 않는다.
3. 트리가 모든 정점을 포함할 때까지 2를 반복한다.

시작점은 어디라도 상관없다. 어디서 출발하든 매 단계의 선택이 항상 어떤 MST에 포함된다는 사실은 아래 정확성 증명에서 따라온다. 이는 두 가지를 구분해서 봐야 한다. 시작점이 달라도 같은 MST가 나올 수 있고, 또 동률(tie) 간선이 있을 때는 그것을 깨는 방식에 따라 여러 MST 중 하나가 나올 수 있다. 어느 쪽이든 결과는 모두 정답이다.

빨간색으로 채워진 정점은 그 단계까지 트리에 들어온 정점 전체이고, 굵은 빨간 선도 그때까지 선택된 간선 전체다. 단계마다 하나씩 늘어난다. 위 예시는 정점 A에서 시작해 A-B, B-C, B-D를 차례로 선택하며, $|V| = 4$이므로 3개의 간선이 추가되면 종료된다. 선택된 간선들의 가중치 합은 7이다.

---

Pseudo-code (개념용)

아래는 알고리즘의 개념을 그대로 옮긴 의사 코드다. 매 반복마다 컷을 가로지르는 간선을 다시 훑는 형태로, 실제 구현에서 쓰는 우선순위 큐 최적화는 뒤에서 따로 다룬다.

// G = (V, E, w), 시작 정점 s
T   = {}            // 선택된 간선 집합
V_T = { s }         // 현재 트리에 포함된 정점 집합

while (V_T != V) {
    // V_T와 V \ V_T 사이를 잇는 간선 중 가장 작은 weight 선택
    (u, v) = argmin {
        w(e) : e = (u, v), u in V_T, v not in V_T
    };
    T   = T ∪ { (u, v) };
    V_T = V_T ∪ { v };
}
return T;

각 반복은 정점 하나를 트리에 추가한다. 시작 시 정점이 1개이고 끝났을 때 $n$개이므로, 반복은 정확히 $n - 1$번 일어난다. 따라서 선택된 간선도 $n - 1$개로, 트리의 간선 수와 일치한다.

이 알고리즘은 입력 그래프가 연결되어 있다는 전제 위에서 동작한다. 연결되어 있지 않다면 어느 단계에서 $V_T$와 $V \setminus V_T$ 사이를 잇는 간선이 없어 argmin이 정의되지 않는다. 이때는 MST 자체가 존재하지 않으며, 각 연결 성분마다 Prim을 따로 돌리면 최소 신장 숲(minimum spanning forest)을 얻는다.

---

구현과 시간 복잡도

위 개념용 의사 코드를 곧이곧대로 구현하면, 매 반복마다 컷을 가로지르는 간선을 모두 다시 훑어야 한다. 실제 구현에서는 각 바깥 정점 $v$까지의 “현재 트리로부터의 최소 연결 비용”을 dist[v]에 저장하고, 이를 최소 힙(min heap) 으로 관리해 가장 싼 정점을 빠르게 꺼낸다.

// dist[v]: v를 현재 트리에 잇는 최소 간선 가중치 (초기 ∞, dist[s]=0)
// parent[v]: MST에서 v의 부모, visited[v]: v가 트리에 들어갔는지
min-heap에 (0, s) 삽입;
while (heap이 비어있지 않음) {
    (d, u) = heap에서 최소 원소 추출;
    if (visited[u]) continue;        // 이미 트리에 있으면 건너뜀
    visited[u] = true;               // u를 트리에 확정
    for (each edge (u, v, w)) {
        if (!visited[v] && w < dist[v]) {
            dist[v] = w; parent[v] = u;
            heap에 (w, v) 삽입;
        }
    }
}

heap에서 꺼낸 정점이 이미 방문되었으면 건너뛰는 것이 핵심이다. 구현 방식에 따라 복잡도가 달라진다.

구현 방식	시간	공간	적합한 그래프
매 반복 컷 간선 전부 탐색	$O(VE)$	인접 리스트 $O(V + E)$	작은 그래프
인접 행렬 + 배열에서 최소 선택	$O(V^2)$	인접 행렬 $O(V^2)$	밀집 그래프 (간선 많음)
인접 리스트 + 이진 힙	$O(E \log V)$	인접 리스트 $O(V + E)$, 힙 $O(E)$	희소 그래프 (간선 적음)

간선이 적은 희소 그래프에서는 이진 힙 구현이, 간선이 빽빽한 밀집 그래프에서는 $O(V^2)$ 구현이 유리하다. 세 구현 모두 dist·parent·visited 배열로 $O(V)$를 따로 쓰지만, 위 표의 항에 묻힌다.

$O(E \log V)$가 성립하는 전제. 위 코드는 dist[v]가 줄어들 때마다 힙에 새 항목을 넣고, 꺼낼 때 방문 여부로 걸러내는 lazy 방식이다. 항목을 넣는 일이 간선을 훑을 때마다 일어날 수 있으므로 힙에는 최대 $E$개가 쌓인다. 공간이 $O(E)$인 것도 여기서 나온다. 연산 하나가 $O(\log E)$이므로 곧이곧대로 세면 $O(E \log E)$다.

여기서 $\log E = O(\log V)$로 바꾸려면 단순 그래프, 즉 중복 간선이 없어야 한다. 그러면 $E \le \binom{V}{2}$이므로 $\log E \le \log V^2 = 2 \log V$다. 중복 간선을 허용하면 $E$가 $V$와 무관하게 커질 수 있어 이 치환이 막히고 $O(E \log E)$가 그대로 남는다. 가중치 비교와 힙 연산은 단위 비용으로 센다.

---

Prim은 어떤 MST를 찾는가

MST는 유일하지 않을 수 있다는 것을 다시 떠올리자. 가중치가 같은 간선이 여러 개라면 동률(tie)을 어떻게 깨느냐에 따라 다른 MST가 나온다.

위 그림은 앞의 진행 예시와 다른 그래프를 사용한다. 동률 간선을 어떻게 깨느냐에 따라 서로 다른 두 MST가 나오지만, 둘 다 가중치 합이 4로 같은 정답이다.

Prim 알고리즘은 그중 하나의 MST를 찾는다. 어떤 간선이 선택되는지는 구현이 동률을 어떻게 깨는지에 따라 다르다. 정리하면:

• MST가 유일하다면 Prim은 그 유일한 답을 찾는다.
• MST가 여러 개라면 Prim은 그중 하나를 찾는다. 어느 것이든 똑같이 정답이다.

참고로 모든 간선 가중치가 서로 다르면 MST는 유일하다(충분조건). 다만 그 역은 성립하지 않는다. 가중치가 같은 간선이 있어도 MST가 여전히 하나뿐일 수 있다.

---

정확성 증명

Prim 알고리즘이 항상 MST를 출력함을 증명한다. 핵심은 다음 불변식이다.

불변식: Prim 알고리즘이 진행되는 도중의 간선 집합 $T_p$는 항상 어떤 MST $T_{mst}$의 부분집합이다. 즉, $T_p \subseteq T_{mst}$인 MST가 적어도 하나 존재한다.

알고리즘이 종료할 때 $|T_p| = n - 1 = |T_{mst}|$이므로, 부분집합 관계와 크기가 같다는 사실로부터 $T_p = T_{mst}$. 따라서 Prim의 출력 $T_p$는 MST다.

기초 — $|T_p| = 0$

처음에는 $T_p = \emptyset$. 공집합은 임의의 MST의 부분집합이다. 성립.

귀납 단계 — $|T_p| = k$에서 $|T_p| = k + 1$로

귀납 가정: $T_p \subseteq T_{mst}$인 MST $T_{mst}$가 존재. 알고리즘이 다음 간선 $e$를 선택해 $T_p' = T_p \cup \{e\}$로 확장했다고 하자. 두 경우로 나눈다.

경우 1: $e \in T_{mst}$

이미 $T_p \subseteq T_{mst}$이고 $e \in T_{mst}$이므로 $T_p' \subseteq T_{mst}$. 불변식이 그대로 유지된다.

경우 2: $e \notin T_{mst}$

이 경우, $T_p'$는 $T_{mst}$의 부분집합이 아니다. 따라서 $T_p'$를 부분집합으로 가지는 다른 MST가 존재함을 보여야 한다.

$T_{mst}$는 모든 정점을 잇는 트리이므로, $e$의 두 끝점을 잇는 경로가 $T_{mst}$ 안에 이미 존재한다. 거기에 $e$를 추가하면 사이클이 생긴다.

사이클 위에는 $e$ 말고도 적어도 하나의 다른 간선 $e'$이 있다. 그런 $e'$이 반드시 존재하는 이유는 이렇다. $e$ 자체가 현재 트리 $V_{T_p}$ 안의 정점과 밖의 정점을 잇는 간선이므로, $e$를 포함한 사이클은 트리 안에서 시작해 밖으로 나갔다가 다시 안으로 돌아온다. 따라서 사이클을 따라가다 보면 트리 안팎을 가르는 컷을 $e$ 말고도 한 번 더 넘는 지점이 있고, 그 지점의 간선이 바로 $e'$이다. 이 $e'$은 다음을 만족하도록 고를 수 있다.

• $e'$의 한 끝점은 현재 트리 $V_{T_p}$ 안에 있고, 다른 끝점은 그 밖에 있다. 즉 $e'$ 역시 Prim의 다음 선택 후보다.
• $e' \in T_{mst}$, 그리고 $e' \notin T_p$.

이제 $e$와 $e'$의 가중치를 비교한다.

경우	결론
$w(e) < w(e')$	$T_{mst}$에서 $e'$을 빼고 $e$를 넣으면 비용이 더 작아지므로, $T_{mst}$가 MST라는 가정에 모순
$w(e) > w(e')$	$e'$도 Prim의 후보였는데 더 무거운 $e$를 골랐으므로, 알고리즘 정의에 모순
$w(e) = w(e')$	$T_{mst}$에서 $e'$을 빼고 $e$를 넣어도 비용 동일. 이 새로운 트리도 MST다

세 경우 중 $w(e) = w(e')$만 가능하다. 이 경우 새로운 MST를 다음과 같이 잡는다.

$$T_{mst}' = (T_{mst} \setminus \{e'\}) \cup \{e\}$$

• $T_{mst}'$은 여전히 MST다. 비용이 같고($w(e) = w(e')$) 정점 집합도 그대로이며, 사이클에서 간선 $e'$ 하나를 빼면 다시 연결된 비순환 그래프, 즉 트리가 되기 때문이다.
• $T_p' \subseteq T_{mst}'$ (원래 $T_p \subseteq T_{mst}$였고, $e'$은 어차피 $T_p$에 없었으며, 이제 $e$도 $T_{mst}'$에 들어 있다).

따라서 불변식이 $T_{mst}'$에 대해 유지된다.

귀납에 의해 알고리즘 종료 시점까지 불변식이 유지되고, Prim의 출력은 항상 MST다.