탐욕 알고리즘으로 최소 신장 트리 설계하기: Kruskal과 Prim의 선택 기준

최소 신장 트리(MST)는 각 단계에서 가장 유리해 보이는 선택을 누적해도 전체 비용을 최소화할 수 있는 대표적인 문제다. 이 성립 조건을 설명하는 축이 탐욕 선택 성질과 최적 부분 구조이며, Kruskal과 Prim은 이를 서로 다른 방식으로 구현한다.

국소 선택이 전체 해에 포함될 수 있는 조건

탐욕 선택 성질(Greedy Choice Property)은 매 단계의 국소 최선 선택이 전체 최적해로 확장될 수 있음을 보장하는 성질이다. 달리 말하면, 어떤 최적해에는 탐욕 규칙이 선택한 첫 항목이 포함될 수 있어야 한다.

MST에서는 컷 속성(Cut Property)이 이 근거가 된다. 그래프를 둘로 나누는 임의의 컷을 가로지르는 최소 가중치 간선은 어떤 MST에 반드시 포함될 수 있다. Kruskal과 Prim이 최소 간선을 안전하게 채택하는 이유도 여기에서 나온다.

최적 부분 구조(Optimal Substructure)도 함께 필요하다. 한 간선을 고른 뒤 남는 문제는 원래 문제와 같은 형태의 하위 MST 문제로 환원되며, 그 하위 문제의 최적해가 전체 해를 구성한다. 간선을 선택하거나 정점을 확장한 뒤 그래프가 축약·분할되는 과정이 이에 해당한다.

탐욕 선택이 최적해와 다를 수 있다는 의문은 교환 논법(Exchange Argument)으로 다룬다. 기존 최적해의 선택을 탐욕 선택으로 교체해도 비용이 늘지 않음을 보이는 방식이다. 더 일반적으로 독립성 체계가 마트로이드(Matroid) 조건을 만족하면 가중치 기반 탐욕 알고리즘은 최적해를 보장한다. 그래프에서 사이클을 만들지 않는 간선 집합으로 이루어진 그래픽 마트로이드는 MST 탐욕 최적성의 기반이다.

선택 규칙과 불변식을 구현에 반영하는 방법

탐욕 알고리즘은 선택 규칙이 모호하면 재현하기 어렵다. 정렬이나 우선순위를 기준으로 규칙을 명시하고, 가중치가 같을 때는 입력 인덱스 같은 결정적 타이브레이킹을 둬야 결과를 재현할 수 있다.

선택이 제약을 위반하지 않는지도 매 단계 확인해야 한다. MST라면 사이클을 만들지 않는지, 연결 가능한 영역을 확장하는지가 핵심이다. 부분해가 무사이클 상태를 유지하고 탐욕 선택의 접두부가 유효하다는 불변식이 구현과 검증의 기준이 된다.

정당성은 컷·사이클 속성, 교환 논법, 귀납 구조로 검증할 수 있다. 구현 성능에서는 Kruskal의 Union-Find와 Prim의 우선순위 큐가 중심 역할을 한다. 정렬과 힙 연산이 비용을 지배하므로, 희소·밀집 그래프 여부와 분산·스트리밍 환경의 데이터 흐름이 알고리즘 선택에 직접 영향을 준다.

간선을 정렬해 연결하는 Kruskal

Kruskal은 모든 간선을 가중치 오름차순으로 정렬한 뒤, 서로 다른 컴포넌트를 잇는 간선만 채택한다.

1. 간선을 가중치 오름차순으로 정렬한다.
2. 각 정점을 독립 집합으로 둔 Union-Find를 초기화한다.
3. 정렬된 간선을 순회하며 두 정점이 다른 집합에 있을 때만 Union한다.
4. 선택한 간선 수가 |V|-1이 되면 MST를 반환한다.

사이클 속성(Cycle Property)에 따르면 사이클 안의 최대 가중치 간선은 MST에서 제외할 수 있다. 컷 속성과 함께 이 성질은 Kruskal의 선택이 안전하다는 근거가 된다.

정렬에 O(E log E)가 들고 합집합·찾기 연산은 거의 O(1)에 수렴하므로 전체 복잡도는 O(E log E)다. E ≈ V인 희소 그래프에서 효율적이며, 배치 처리와 병렬 정렬에 맞추기 쉽다.

한 정점에서 트리를 넓히는 Prim

Prim은 시작 정점에서 출발해 현재 트리와 연결되는 가장 가벼운 간선을 반복 선택한다.

1. 임의의 시작 정점 s를 정한다.
2. 우선순위 큐에 s의 키를 0으로 넣는다.
3. 최소 키 정점을 꺼내 트리에 추가하고, 인접 간선으로 키를 완화한다.
4. 큐가 빌 때까지 반복해 MST를 구성한다.

현재 트리와 아직 포함되지 않은 정점을 가르는 컷에서 최소 간선을 선택한다는 점에서 Prim도 컷 속성을 따른다. 바이너리 힙과 인접 리스트를 쓰면 O(E log V), 피보나치 힙을 쓰면 이론적으로 O(E + V log V)의 상한을 갖는다. 다만 피보나치 힙은 구현 복잡도를 함께 고려해야 한다.

⤢✕

그래프 형태와 처리 방식에 따른 선택

관점	Kruskal	Prim
성능	O(E log E), 희소 그래프·간선 리스트 적합	O(E log V), 밀집 그래프·인접 리스트/힙 적합
확장성	정렬 병렬화·컴포넌트 병합 용이	지역적 확장, 대규모 메모리 지역성 우수
일관성	가중치 동률 시 타이브레이크 필요, MST 비유일 가능	동일, 시작점·동률 규칙에 따라 MST 달라질 수 있음
안정성	Union-Find로 사이클 제어 안정, 배치 친화	힙 오퍼레이션 안정, 스트리밍 엣지에 유리
운영 편의	구현 단순, 파일 기반 대용량 간선 처리 용이	온라인/증분 갱신 용이, 특정 서브그래프부터 확장 쉬움

네트워크나 배선 비용을 최소화할 때는 데이터센터 랙-토폴로지와 광케이블 길이 설계에 MST를 적용할 수 있다. 수십만 링크로 이루어진 희소 그래프에서는 Kruskal을 이용해 비용 절감과 검증을 자동화할 수 있다.

망 복구와 스패닝 트리 구성에서는 L2/L3 토폴로지의 지연·손실률을 가중치로 사용해 복구 트리를 만들 수 있다. 지연을 다시 측정한 뒤에는 Prim으로 근접 라우터부터 재계산해 영향 범위를 줄이는 방식이 가능하다.

파일 동기화나 유사도 그래프의 리소스 클러스터링에도 최소 간선 연결을 이용할 수 있다. 대규모 배치 처리에서는 Kruskal과 외부 정렬(External Sort)을 결합한다. Dijkstra의 비음수 가중 최단경로, Huffman 코딩처럼 다른 탐욕 계열 알고리즘과 함께 파이프라인을 구성하는 경우도 있다.

희소 그래프를 예로 들면 V=10^5, E=10^6일 때 Kruskal의 정렬 비용은 ≈ E·log2(E) ≈ 10^6·20 ≈ 2×10^7 비교 연산 규모다. Prim에서 바이너리 힙을 사용하면 E log V ≈ 10^6·17 ≈ 1.7×10^7 힙 연산 규모가 된다. 구현, 메모리, I/O 접근 패턴에 따라 두 방식 모두 실용적이며, 간선 스트리밍에는 Prim, 외부 정렬이 가능한 환경에는 Kruskal이 우위다.

Python으로 구현할 때 확인할 점

환경은 Python 3.10+를 전제로 하며, 그래프는 무방향 가중 그래프로 표현한다. 정점은 0..n-1 범위를 사용하고, 희소 그래프에는 인접 리스트가 적합하다.

Kruskal에서는 Union-Find의 경로 압축과 랭크 기반 합치기로 사이클을 판별한다.

from typing import List, Tuple

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

def kruskal_mst(n: int, edges: List[Tuple[int, int, float]]) -> Tuple[float, List[Tuple[int, int, float]]]:
    """edges: (u, v, w) 무방향 간선 리스트. 연결 그래프가 아니면 포리스트 반환."""
    edges_sorted = sorted(edges, key=lambda x: (x[2], x[0], x[1]))  # 안정적 타이브레이크
    uf = UnionFind(n)
    mst, total = [], 0.0
    for u, v, w in edges_sorted:
        if uf.union(u, v):
            mst.append((u, v, w))
            total += w
            if len(mst) == n - 1:
                break
    return total, mst

Prim은 우선순위 큐에 후보 간선을 넣고 가장 가벼운 연결을 꺼내는 방식으로 구현한다.

import heapq
from typing import List, Tuple

def prim_mst(n: int, adj: List[List[Tuple[int, float]]], start: int = 0) -> Tuple[float, List[Tuple[int, int, float]]]:
    """adj[u] = [(v, w), ...]. 연결 그래프 가정. 비연결이면 컴포넌트별로 반복 실행."""
    visited = [False] * n
    pq: List[Tuple[float, int, int]] = []  # (가중치, 부모, 정점)
    heapq.heappush(pq, (0.0, -1, start))
    total, mst = 0.0, []
    while pq:
        w, p, u = heapq.heappop(pq)
        if visited[u]:
            continue
        visited[u] = True
        total += w
        if p != -1:
            mst.append((p, u, w))
        for v, w2 in adj[u]:
            if not visited[v]:
                heapq.heappush(pq, (w2, u, v))
    # 비연결 그래프 처리: 미방문 정점 있으면 추가 컴포넌트도 확장
    for s in range(n):
        if not visited[s]:
            tw, sub = prim_mst(n, adj, s)
            total += tw
            mst.extend(sub)
    return total, mst

동률 가중치는 (weight, stable_order)처럼 정렬 키를 확장해 처리하면 재현성을 확보할 수 있다. 대용량 간선은 온디스크 머지정렬을 포함한 외부 정렬 뒤 Kruskal로 처리하고, 스트리밍 간선에는 Prim을 고려할 수 있다. MST는 음수 가중치에도 문제가 없지만, 실수 가중치를 비교할 때는 상대·절대 오차 허용치를 적용한다.

성능뿐 아니라 검증 가능성도 남긴다

희소 그래프에서는 O(E log V) 또는 O(E log E)로 선형 로그급 성능을 기대할 수 있다. 밀집 그래프에서는 인접 행렬을 쓰는 Prim의 O(V^2) 변형도 캐시 적중률로 실무 효율성을 확보할 수 있다.

Union-Find와 힙은 메모리·연산의 상수 계수를 줄이는 데 도움이 되며, 배치와 온라인 처리 모두에 맞춰 파이프라인을 구성할 수 있다. 컷·사이클 속성과 교환 논법으로 선택의 정당성을 검증하고, 결정적 타이브레이킹과 불변식 점검으로 테스트도 수월해진다.

다만 탐욕 성질이 성립하지 않는 문제에서는 근사해나 부분 최적해에 머물 수 있다. 피보나치 힙은 이론적 이점이 있지만 구현 복잡도와 상수 비용이 증가한다. 그래프의 희소성·밀집도, 배치·스트리밍 접근 방식, 메모리와 I/O 조건을 함께 놓고 선택해야 한다.