최소신장트리로 연결 비용을 줄이는 방법

모든 지점을 연결하되 불필요한 링크를 남기지 않는 구조

최소신장트리(Minimum Spanning Tree, MST)는 연결 그래프의 모든 정점을 포함하면서 사이클을 만들지 않고, 선택한 간선 가중치 합을 가장 작게 만드는 트리다. 통신망, 도로망, 전력망처럼 연결 자체는 보장해야 하지만 구축 비용은 제한해야 하는 문제에서 기본 구조로 쓰인다.

신장트리(Spanning Tree)는 연결 그래프 G(V, E)의 모든 정점을 포함하는 사이클 없는 부분 그래프다. 정점이 n개라면 간선은 n-1개가 된다. 이 신장트리들 가운데 간선 가중치 합이 최소인 것이 MST다. 가중치가 모두 서로 다를 때는 MST가 유일하다.

그래프가 연결되지 않았다면 하나의 MST를 만들 수 없다. 이 경우 각 연결 성분에서 MST를 구한 뒤 묶는 최소신장포리스트(Minimum Spanning Forest, MSF)로 문제를 다뤄야 한다.

간선 선택에 적용되는 성질

MST의 선택 규칙은 컷 속성(Cut Property)과 사이클 속성(Cycle Property)으로 설명할 수 있다.

어떤 컷을 가로지르는 간선 중 가중치가 가장 작은 간선은 MST에 포함된다. 반대로 하나의 사이클에서 가장 무거운 간선은 MST에 들어갈 수 없다. 알고리즘이 간선을 고르는 이유와 결과를 검증하는 기준도 이 두 성질에서 나온다.

가중치는 비음수인 비용 모델이 일반적이다. 음수 가중치도 사용할 수 있지만, 그것이 비용으로 어떤 의미를 갖는지는 별도로 확인해야 한다. 입력 그래프의 연결성도 전제 조건이다. 연결성이 보장되지 않는 입력을 받을 수 있다면 예외를 낼지, 포리스트를 반환할지를 먼저 정해야 한다.

그래프 형태에 따라 달라지는 선택 방식

Kruskal 알고리즘은 모든 간선을 가중치 오름차순으로 정렬한 뒤, 사이클을 만들지 않는 간선만 차례로 채택한다. 서로 다른 집합인지 빠르게 확인하기 위해 Disjoint Set Union(Union-Find)을 사용하며, 경로 압축과 랭크 최적화를 적용한다. 간선 수가 상대적으로 적은 희소 그래프에 적합하다.

Prim 알고리즘은 하나의 시작 정점에서 출발해 현재 트리에 연결할 수 있는 가장 가벼운 간선을 계속 확장한다. 우선순위 큐와 방문 집합이 핵심이며, 이진 힙을 주로 사용한다. 인접 리스트나 인접 행렬을 이미 보유한 환경, 특히 밀집 그래프에서 선택하기 좋다. 밀집 그래프에서는 배열 기반 O(V^2) 구현도 실용적이다.

Kruskal은 간선 리스트 입력을 다루기 직관적이고 간선 스트리밍 처리에 유리하다. Prim은 시작 정점과 우선순위 큐 정책에 따라 결과가 결정되므로, 동률 간선을 다룰 때는 재현성 규칙을 정해두는 편이 좋다.

항목	Kruskal	Prim
성능	O(E log E)	O(E log V) [힙], O(V^2) [배열]
확장성	희소 그래프 유리, 간선 스트리밍 처리 용이	밀집 그래프 유리, 큰 V에서도 안정
일관성	간선 타이브레이킹 규칙 필요(결과 재현성 보장)	시작 정점·우선순위 큐 정책에 따라 결정
안정성	Union-Find로 사이클 안전 차단	방문 집합으로 일관된 확장
운영 편의	간선 리스트 입력 직관적	인접 리스트/행렬 보유 시 구현 단순

입력 검증부터 결과 확인까지의 흐름

⤢✕

Kruskal은 간선을 정렬하고 Union-Find를 초기화한 뒤, 가벼운 간선부터 검사한다. 서로소 집합을 연결하는 간선만 선택하며, |V|-1개를 선택하면 완료된다. 시간 복잡도는 O(E log E), 공간 복잡도는 O(V)다.

Prim은 임의의 시작 정점 s에서 인접 간선을 우선순위 큐에 넣고 시작한다. 큐에서 최소 간선을 꺼내 미방문 정점으로 향하는 경우에만 채택한 뒤, 새 정점의 인접 간선을 확장한다. |V|개 정점을 방문하면 끝나며, 이진 힙 기준 시간 복잡도는 O(E log V)다.

Python 구현으로 확인하는 Kruskal과 Prim

정점은 0..n-1 정수이며, 무방향 연결 그래프를 가정한다. 연결되지 않은 그래프는 예외를 발생시킨다.

# Python 3.10+
from heapq import heappush, heappop

def kruskal(n, edges):
    # edges: list of (w, u, v)
    parent = list(range(n))
    rank = [0] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb:
            return False
        if rank[ra] < rank[rb]:
            parent[ra] = rb
        elif rank[ra] > rank[rb]:
            parent[rb] = ra
        else:
            parent[rb] = ra
            rank[ra] += 1
        return True

    total, mst = 0, []
    for w, u, v in sorted(edges):
        if union(u, v):
            mst.append((u, v, w))
            total += w
            if len(mst) == n - 1:
                break
    if len(mst) != n - 1:
        raise ValueError("그래프가 연결되지 않음: Spanning Forest가 아님")
    return total, mst

def prim(n, adj, start=0):
    # adj: list of list, adj[u] = [(v, w), ...]
    visited = [False] * n
    visited[start] = True
    pq = []
    for v, w in adj[start]:
        heappush(pq, (w, start, v))

    total, mst, count = 0, [], 1
    while pq and count < n:
        w, u, v = heappop(pq)
        if visited[v]:
            continue
        visited[v] = True
        count += 1
        mst.append((u, v, w))
        total += w
        for nv, nw in adj[v]:
            if not visited[nv]:
                heappush(pq, (nw, v, nv))
    if count != n:
        raise ValueError("그래프가 연결되지 않음: Spanning Forest가 아님")
    return total, mst

if __name__ == "__main__":
    # 예시 그래프
    n = 6
    edges = [
        (4, 0, 1), (3, 0, 2), (1, 1, 2),
        (2, 1, 3), (4, 2, 3), (2, 3, 4),
        (6, 4, 5), (5, 2, 5),
    ]
    # 인접 리스트 구성
    adj = [[] for _ in range(n)]
    for w, u, v in edges:
        adj[u].append((v, w))
        adj[v].append((u, w))

    total_k, mst_k = kruskal(n, edges)
    total_p, mst_p = prim(n, adj, start=0)

    print("Kruskal MST weight:", total_k, "edges:", mst_k)
    print("Prim    MST weight:", total_p, "edges:", mst_p)

예시에서는 두 알고리즘 모두 총 가중치 13, 간선 5개(n-1)를 산출한다. 그래프가 비연결이면 ValueError가 발생한다. 운영 정책에 따라 이 예외를 성분별 MST(MSF) 반환으로 바꿀 수 있다.

연결 비용과 운영 복잡도를 함께 낮추는 곳

통신과 네트워크 설계에서는 라우팅 백본, 광망의 링-트리 하이브리드 구성에서 링크 비용을 줄이는 데 활용한다. 장애를 허용해야 한다면 MST 기반 기본 경로에 여분 링크를 더하는 방식으로 설계할 수 있다.

데이터센터와 클러스터에서는 랙 사이의 최소 케이블 구성을 찾는 데 쓰이며, 케이블 길이와 포트 수에 따른 운영 비용을 줄이는 기준이 된다. 이미지 처리와 머신러닝에서는 그래프 기반 군집화(single-linkage), 초점 영역 분할(Region Merging)에서 경계 비용을 낮추는 데 활용된다. 전력과 도로 인프라에서는 송전선·도로망의 초기 구축 비용을 최소화하고, 단계적 확장에서는 MST와 증분 설계를 함께 적용한다.

무차별 연결과 비교하면 그래프 밀도와 비용 분포에 따라 링크 비용을 15~40% 절감할 수 있다. 사이클이 없으므로 라우팅 루프와 브로드캐스트 스톰 위험을 제거하고, 제어 플레인의 복잡도도 낮춘다. 희소한 대규모 그래프는 O(E log E) 또는 O(E log V)로 수백만 간선까지 실용적으로 처리할 수 있다.

동일 가중치 간선이 존재한다면 정점이나 간선 ID 우선순위 같은 타이브레이킹 규칙을 고정해야 한다. 그래야 같은 입력에서 같은 MST 결과를 재현할 수 있다.