최소신장트리(MST): 연결 비용을 최소화하는 그래프 설계
최소신장트리(MST)의 최적성 원리와 Kruskal·Prim·Borůvka 선택 기준, 네트워크 설계와 클러스터링 활용 방법을 정리합니다.
2026-08-14 · 최초 발행 2024-04-29
연결 비용을 줄이는 트리의 조건
네트워크, 도로, 전력망처럼 모든 지점을 연결해야 하는 문제에서는 연결 자체보다 어떤 간선을 남길지가 비용을 결정한다. Minimum Spanning Tree(MST)는 가중치가 있는 무방향 연결 그래프에서 전체 정점을 모두 연결하되, 간선 가중치 합이 가장 작은 트리를 찾는다.
스패닝 트리는 무방향 연결 그래프 G=(V, E)에서 모든 정점을 포함하고 사이클이 없는 부분그래프다. 간선 수는 |V|-1이며, 이들 가운데 가중치 합이 최소인 경우가 MST다.
그래프가 불연결이면 하나의 MST는 존재하지 않는다. 이때는 각 컴포넌트의 최소신장트리를 모은 최소신장 숲(MSF)을 구한다. 간선 가중치가 모두 다르면 MST는 유일하지만, 동률이 있으면 여러 해가 가능하다. 음수 가중치도 사용할 수 있으며, 자기 루프는 제외하고 동일 정점쌍의 다중 간선은 허용된다.
알고리즘 선택을 좌우하는 그래프 형태
희소 그래프는 인접 리스트로 표현하는 편이 효율적이고, 밀집 그래프에서는 인접 행렬과 Prim 변형이 유리할 수 있다. Kruskal에는 사이클 검출을 위한 Union-Find(Disjoint Set)가 필요하며, 이 연산은 O(α(n))이다. Prim은 힙 기반 우선순위 큐로 후보 간선을 관리해 O(E log V)에 선택을 수행한다.
Kruskal은 모든 간선을 가중치 오름차순으로 정렬한 뒤, 서로 다른 집합을 연결하는 간선만 채택한다. 희소 그래프와 분산 정렬, 배치 처리에 잘 맞는다.
Prim은 하나의 시작 정점에서 트리를 바깥으로 확장한다. 우선순위 큐에서 최소 비용 간선을 꺼내므로 밀집 그래프나 지속적인 확장 흐름에 적합하다.
Borůvka는 각 컴포넌트가 최소 외부 간선을 동시에 선택해 병합한다. 병렬·분산 환경에서 활용하기 좋다.
| 알고리즘 | 성능 | 확장성 | 일관성 | 안정성 | 운영 편의 |
|---|---|---|---|---|---|
| Kruskal | O(E log E), Union-Find 최적화 시 E log V 근사 | 희소 그래프, 외부정렬·배치 처리 용이 | 정렬·타이브레이크에 좌우 | 음수·다중간선 안전, 불연결 시 MSF | 구현 간단, 병렬 정렬/필터 결합 용이 |
| Prim(이진 힙) | O(E log V) | 밀집 그래프는 Fibonacci 힙 시 O(E + V log V) | 시작점·타이브레이크 영향 | 음수 안전, 연결성 전제 | 스트리밍 확장 자연스러움 |
| Borůvka | 각 라운드 O(E), O(log V) 라운드 | 분산/병렬 매우 우수 | 라운드 동률 선택 규칙 필요 | 컴포넌트 기반 병합 견고 | 구현 복잡도 중간, 클러스터 친화 |
탐욕 선택이 성립하는 이유
MST는 탐욕적으로 간선을 고르지만, 두 가지 성질이 그 선택을 뒷받침한다.
- Cut Property: 임의의 컷을 가르는 간선 가운데 최소 가중치 간선은 MST에 안전하게 포함할 수 있다.
- Cycle Property: 하나의 사이클에서 가장 무거운 간선은 MST에 포함될 수 없다.
알고리즘은 이 성질을 바탕으로 최소 간선을 선택하면서도 사이클을 막고 연결성 제약을 유지한다. 불연결 입력은 컴포넌트별 MSF로 처리하고, 동률 가중치가 있다면 정점 또는 간선 ID 정렬 같은 타이브레이크 규칙으로 재현성을 확보한다. 정수 오버플로우 가능성이 있는 언어에서는 64비트 정수 사용이 권고된다.
설계와 분석에서 MST를 쓰는 곳
광케이블, 회선, 송전선, 도로망에서는 후보 경로와 설치비, 지형 제약을 입력으로 받아 구축 경로 집합을 정한다. 유지보수까지 고려한다면 MST에 최소 가용성 증강을 더해 한두 개의 백업 간선을 추가할 수 있다.
Single-linkage 계층적 클러스터링은 MST에서 가장 무거운 k-1개 간선을 제거해 k개 군집을 만든다. 이미지 세그멘테이션에서는 픽셀 그래프의 유사도 가중치를 바탕으로 영역을 분리한다.
SDN과 데이터센터에서는 루프 방지 스패닝 트리의 초기 토폴로지로 사용할 수 있다. 이후에는 트래픽 기반 가중치 재학습으로 비용을 동적으로 갱신한다. 무선 센서 네트워크도 초기 연결을 구성한 뒤 에너지 제약을 반영한 가중치로 주기적으로 다시 계산할 수 있다.
MST는 근사 최적화의 기준 구조이기도 하다. 메트릭 TSP에서는 MST 기반 Preorder 순회로 2-근사 투어를 만들며, Steiner Tree에서는 터미널 간 MST를 기준 하한 또는 휴리스틱 가이드로 사용한다.
최소 비용 구조에 붙는 운영 제약
MST는 총 가중치 합을 최소화해 설치·전송·유지 비용을 정량적으로 줄인다. O(E log V) 내외 복잡도로 수천만 간선 규모까지 확장할 수 있고, 외부정렬·분산 환경에서는 수억 간선도 처리할 수 있다. 사이클이 사라지면서 제어 평면이 단순해지고 루프 관련 장애도 줄어든다.
다만 최소 비용과 내결함성은 같은 목표가 아니다. 실제 운영에서는 MST 계산 후 제한된冗長 경로를 추가하거나, 최소 컷 여유도에 따라 간선을 보강해 k-연결성을 확보한다. 비용 증가는 복원력 향상과 함께 관리해야 할 트레이드오프다.
대규모 Kruskal 처리에서는 외부정렬을 적용하고, 가중치 상한이나 도메인 제약 같은 스트리밍 필터를 먼저 적용할 수 있다. 분산 환경에서는 Borůvka의 라운드 기반 병합과 컴포넌트 ID 압축으로 통신량을 줄인다. 동률 가중치가 있다면 간선 키를 (가중치, u, v)로 정렬해 결과 결정성을 보장한다.
Python으로 구현하는 Kruskal
환경은 Python 3.10+이며 표준 라이브러리만 사용한다. 입력은 0-index 정점과 (u, v, w) 간선 리스트이고, 무방향 그래프에서 w는 정수 또는 실수다.
# Python 3.10+
from typing import List, Tuple
Edge = Tuple[int, int, float]
class DSU:
def __init__(self, n: int):
self.p = list(range(n))
self.r = [0]*n
def find(self, x: int) -> int:
while self.p[x] != x:
self.p[x] = self.p[self.p[x]]
x = self.p[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.r[ra] < self.r[rb]: ra, rb = rb, ra
self.p[rb] = ra
if self.r[ra] == self.r[rb]: self.r[ra] += 1
return True
def mst_kruskal(n: int, edges: List[Edge]) -> List[Edge]:
# 불연결 시 최소신장 숲 반환
edges_sorted = sorted(edges, key=lambda e: e[2])
dsu = DSU(n)
mst = []
for u, v, w in edges_sorted:
if dsu.union(u, v):
mst.append((u, v, w))
if len(mst) == n - 1: # 연결 그래프인 경우 조기 종료
break
return mst
if __name__ == "__main__":
N = 5
E = [(0,1,4),(0,2,2),(1,2,5),(1,3,10),(2,4,3),(4,3,4)]
result = mst_kruskal(N, E)
cost = sum(w for *_, w in result)
print("MST edges:", result)
print("Total cost:", cost)우선순위 큐로 확장하는 Prim
Prim 구현은 각 컴포넌트에서 시작점을 잡아 우선순위 큐를 확장한다. 따라서 불연결 그래프에서는 MST 대신 최소신장 숲을 반환한다.
# Python 3.10+
from typing import List, Tuple
import heapq
Edge = Tuple[int, int, float]
def mst_prim(n: int, edges: List[Edge]) -> List[Edge]:
# 인접 리스트 구성
adj = [[] for _ in range(n)]
for u, v, w in edges:
adj[u].append((w, v, u))
adj[v].append((w, u, v))
visited = [False]*n
mst = []
# 불연결 그래프 지원: 각 컴포넌트마다 시작
for s in range(n):
if visited[s]: continue
visited[s] = True
heap = []
for w, v, u in adj[s]:
heapq.heappush(heap, (w, s, v))
while heap:
w, u, v = heapq.heappop(heap)
if visited[v]: continue
visited[v] = True
mst.append((u, v, w))
for w2, v2, _ in adj[v]:
if not visited[v2]:
heapq.heappush(heap, (w2, v, v2))
return mst # 연결 그래프면 |V|-1개, 아니면 MSF
if __name__ == "__main__":
N = 5
E = [(0,1,4),(0,2,2),(1,2,5),(1,3,10),(2,4,3),(4,3,4)]
result = mst_prim(N, E)
cost = sum(w for *_, w in result)
print("MST/Forest edges:", result)
print("Total cost:", cost)