길리랩blog

최소 신장 트리에서 Kruskal과 Prim을 고르는 기준

최소 신장 트리의 컷·사이클 성질과 Kruskal, Prim, Union-Find 구현 방식, 그래프 밀도별 선택 기준을 정리합니다.

2026-08-14 · 최초 발행 2024-04-29

비용이 가장 낮은 연결 구조

최소 신장 트리(Minimum Spanning Tree, MST)는 연결된 가중치 무방향 그래프에서 모든 정점을 잇되, 선택 간선의 가중치 합을 최소로 만드는 구조다. 네트워크 설계, 클러스터링, 이미지 처리처럼 연결은 유지하면서 비용과 구조 복잡도를 줄여야 하는 문제에서 사용한다.

입력 그래프를 G=(V, E, w)라고 할 때 w: E→R이고, 결과 T⊆E는 모든 정점을 연결하면서 사이클을 만들지 않아야 한다. 연결 그래프라면 |V|-1개의 간선으로 트리를 구성한다. 그래프가 비연결 상태라면 하나의 MST 대신 연결 컴포넌트마다 최소 신장 트리를 구성한 최소 신장 포리스트(MSF)를 얻는다.

MST의 선택은 다음 성질로 뒷받침된다.

  • 컷 성질: 임의의 컷을 가로지르는 간선 중 가중치가 가장 작은 간선은 어떤 MST에도 포함된다.
  • 사이클 성질: 임의의 사이클에서 가중치가 가장 큰 간선은 어떤 MST에도 포함되지 않는다.
  • 모든 간선 가중치가 서로 다르면 MST는 유일하다. 동률이 있으면 정렬 안정성이나 타이브레이킹 규칙에 따라 여러 결과가 나올 수 있다.

그래프 형태에 맞춰 Kruskal과 Prim 선택하기

간선 수가 |E|≈|V|인 스파스 그래프는 간선 리스트와 정렬 중심 접근이 잘 맞는다. 반대로 |E|≈|V|^2인 덴스 그래프에서는 인접 행렬 기반 Prim이나 고급 힙 구조를 고려할 수 있다. 알고리즘 자체보다 그래프 표현과 밀도에 맞는 자료구조 조합이 선택의 기준이 된다.

Kruskal은 간선을 가중치 오름차순으로 정렬한 뒤, 사이클을 만들지 않는 간선만 순서대로 채택한다. 사이클 판정은 Union-Find(Disjoint Set Union, DSU)가 맡는다. 정렬 비용이 대부분을 차지하므로 시간 복잡도는 O(E log E)다.

Prim은 하나의 시작 정점에서 현재 트리 바깥으로 이어지는 최소 가중치 간선을 반복해서 고른다. 이진 힙 우선순위 큐를 쓰면 O(E log V)이며, 덴스 그래프에서 효과적이다. 방문 집합 관리와 키 감소(Decrease-Key) 전략을 구현 시 함께 검토해야 한다.

DSU는 대표자를 찾는 Find와 두 집합을 합치는 Union 연산을 제공한다. 경로 압축(path compression), 랭크 또는 사이즈 기반 병합을 적용하면 역아커만 함수 α(V) 수준의 거의 상수 시간으로 동작한다. Kruskal에서는 이 구조가 컴포넌트 추적과 사이클 판정을 담당한다.

음수와 0 가중치는 사용할 수 있다. 자체 루프는 제외하고, 중복 간선은 최소 가중치 간선만 실질적인 후보가 된다. 비연결 입력은 사전에 확인하거나, 처리 후 컴포넌트 수와 채택 간선 수를 검사해야 한다. 동률 간선이 많다면 간선 ID나 정점 인덱스를 기준으로 정렬 규칙을 고정해 결과를 재현 가능하게 만드는 편이 낫다.

간선 선택이 진행되는 흐름

⤢✕KruskalFind(u)!=Find(v)그 외예아니오Prim아니오예아니오예입력: 가중치 무방향 그래프알고리즘 선택간선 리스트 정렬 O(E log E)DSU 초기화: 각 정점 독립 집합간선 (u,v,w) 순회Union(u,v), 간선 채택건너뛰기(사이클 예방)간선 수 == V-1?MST 출력시작 정점 선택우선순위 큐에 인접 간선 푸시큐 비었는가?최소 간선 팝목표 정점 미방문?간선 채택, 정점 방문, 새 인접간선 푸시

입력 단계에서는 무방향 그래프인지, 가중치가 유효한지 확인하고 자기 루프를 제거한다. 처리 후 채택 간선 수가 V-1보다 작으면 MST는 존재하지 않으며, 컴포넌트별 결과를 MSF로 반환한다. 동률 간선은 안정 정렬이나 명시적 타이브레이킹 키로 처리한다.

알고리즘 성능(시간복잡도) 그래프 밀도 동률 처리 입력 예외 구현 관점
Kruskal O(E log E) + O(E α(V)) 스파스 그래프에 유리, 덴스 그래프에서는 정렬 비용 부담 정렬·타이브레이킹으로 재현성 확보가 쉬움 음수 허용, 루프 무시, 중복 간선 중 최소만 유효 간선 정렬과 DSU 필요, 구현 단순
Prim(이진 힙) O(E log V) 덴스·중간 밀도 그래프에 유리 시작점을 고정하면 재현성 확보 음수 허용, 루프·중복 간선 필터 필요 인접 리스트와 PQ, 키 감소 패턴 필요

Python으로 확인하는 Kruskal과 Prim

전제는 Python 3.9+와 0..n-1 정점 인덱스를 쓰는 무방향 그래프다. 샘플 그래프는 V=5, E={(0,1,1),(0,2,3),(1,2,1),(1,3,4),(2,3,1),(3,4,2)}로 둔다.

# Kruskal with Union-Find (DSU)
# Python 3.9+

class DSU:
    def __init__(self, n):
        self.p = list(range(n))
        self.r = [0]*n
    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]  # path halving
            x = self.p[x]
        return x
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.r[a] < self.r[b]:
            a, b = b, a
        self.p[b] = a
        if self.r[a] == self.r[b]:
            self.r[a] += 1
        return True

def kruskal_mst(n, edges):
    # edges: list of (w,u,v) for undirected graph
    dsu = DSU(n)
    mst = []
    total = 0
    edges.sort()  # sort by w
    for w, u, v in edges:
        if u == v:
            continue  # ignore self-loop
        if dsu.union(u, v):
            mst.append((u, v, w))
            total += w
            if len(mst) == n - 1:
                break
    if len(mst) != n - 1:
        # Disconnected: return forest
        pass
    return total, mst

n = 5
edges = [
    (1,0,1),(3,0,2),(1,1,2),(4,1,3),(1,2,3),(2,3,4)
]
total, mst = kruskal_mst(n, edges)
print("Kruskal MST weight:", total)
print("Edges:", mst)
# Prim using binary heap (heapq)
# Python 3.9+

import heapq

def prim_mst(n, adj, start=0):
    visited = [False]*n
    h = []
    visited_count = 0
    mst = []
    total = 0

    def push_edges(u):
        for v, w in adj[u]:
            if not visited[v]:
                heapq.heappush(h, (w, u, v))

    visited[start] = True
    visited_count += 1
    push_edges(start)

    while h and visited_count < n:
        w, u, v = heapq.heappop(h)
        if visited[v]:
            continue
        visited[v] = True
        visited_count += 1
        mst.append((u, v, w))
        total += w
        push_edges(v)

    if visited_count != n:
        # Disconnected: forest total and edges returned
        pass
    return total, mst

n = 5
adj = [[] for _ in range(n)]
for w,u,v in [(1,0,1),(3,0,2),(1,1,2),(4,1,3),(1,2,3),(2,3,4)]:
    adj[u].append((v,w)); adj[v].append((u,w))

total, mst = prim_mst(n, adj, start=0)
print("Prim MST weight:", total)
print("Edges:", mst)

Kruskal은 정렬에 O(E log E), DSU 연산에 O(E α(V))가 들며 전체 복잡도는 O(E log E)다. 이진 힙 Prim은 O(E log V)다. Fibonacci 힙을 사용한 Prim은 덴스 그래프에서 이론상 O(E + V log V)이지만, 구현 복잡성과 상수 비용 때문에 실무 채택은 드물다.

네트워크 설계와 데이터 구조화에 쓰는 방식

통신·전력망에서는 백본과 리프 스위치의 연결을 먼저 최소화하고, 중복 링크는 이후 신뢰성 요구에 따라 추가할 수 있다. 거리, 대역, 장비 비용처럼 지리적 제약과 비용을 가중치로 모델링한 뒤 MST를 1차 설계에 사용한다.

Single-Linkage 클러스터링에서는 유사도 그래프의 MST를 만든 다음 큰 가중치 간선을 잘라 k-클러스터를 도출한다. 고차원 데이터 구조를 단순화하고 노이즈에 견고하게 대응하는 방식이다.

이미지 세그멘테이션에서는 Felzenszwalb-Huttenlocher처럼 지역 경계를 추출하는 데 활용할 수 있다. 경로망 단순화와 메쉬 연결 최소화는 렌더링 비용 절감으로 이어진다.

클라우드 네트워크에서는 VPC와 리전 사이의 필수 피어링을 최소화해 라우팅 복잡도와 전송 비용을 줄이는 기준선으로 삼을 수 있다. 이후에는 신뢰성 목표에 맞춰 링이나 메시 구조를 보강한다.

규모와 운영 조건을 함께 검토하기

|V|=100,000, |E|=300,000인 스파스 그래프에서 이진 힙 Prim은 E log V ≈ 3e5×17 ≈ 5.1e6 우선순위 연산 규모다. Kruskal의 정렬 비용은 E log E ≈ 3e5×18 ≈ 5.4e6 비교 규모에 DSU 비용이 더해지며, DSU 비용은 미미하다. 수천만 간선까지는 단일 노드 처리도 가능하다.

MST는 네트워크 링크, 케이블, 라우터 포트 비용의 합을 최소화한다. 파일럿 측정에서는 설치·운영 CAPEX·OPEX를 10~30% 절감하는 효과를 기대할 수 있으며, 결과는 가중치 모델링 품질에 좌우된다.

결정 규칙을 고정하면 결과를 재현할 수 있어 변경 이력 관리가 쉬워진다. 음수·0 가중치, 중복 간선, 자체 루프 같은 비정상 데이터를 걸러내는 메커니즘도 함께 구현할 수 있다. 스파스 그래프에서 간선 정렬이 중심이라면 Kruskal과 Union-Find를, 덴스 그래프에서 인접 리스트 접근이 중심이라면 Prim과 우선순위 큐를 선택하는 방식이 적합하다.

최소 신장 트리KruskalPrimUnion-Find그래프 알고리즘