Kruskal 알고리즘으로 최소 신장 트리 구성하기
Kruskal 알고리즘의 간선 정렬과 Union-Find 기반 사이클 판별 과정을 정리하고, 최소 신장 트리·포리스트 구성과 그래프 특성별 선택 기준, Python 구현을 설명한다.
2026-08-15 · 최초 발행 2025-08-10
가벼운 간선부터 연결하되 고리는 만들지 않는다
Kruskal 알고리즘은 가중 그래프에서 최소 신장 트리(Minimum Spanning Tree, MST)를 구성하는 그리디 알고리즘이다. Joseph Kruskal이 1956년에 제안했으며, 네트워크 설계나 배관 시스템, 전기 회로처럼 모든 지점을 최소 비용으로 연결해야 하는 문제에 쓸 수 있다.
핵심은 간선을 가중치 순으로 정렬한 뒤, 기존 연결에 사이클을 만들지 않는 간선만 결과에 넣는 데 있다. 그래프가 연결돼 있지 않다면 하나의 트리 대신 각 연결 성분의 최소 신장 포리스트(Minimum Spanning Forest, MSF)를 반환한다.
간선 정렬 뒤 반복하는 선택 규칙
처리는 다음 순서로 진행된다.
- 그래프의 모든 간선을 가중치 오름차순으로 정렬한다.
- 가장 가중치가 작은 간선부터 확인한다.
- 그 간선을 추가해 사이클이 생기지 않으면 결과에 포함하고, 사이클이 생기면 버린다.
- n-1개의 간선을 선택할 때까지, 또는 모든 정점이 연결될 때까지 이 과정을 반복한다.
연결 그래프에서는 선택된 간선이 |V|-1개가 되면 종료할 수 있다. 비연결 그래프에서는 모든 간선을 확인한 뒤 각 연결 성분을 잇는 간선 집합이 남으며, 이것이 최소 신장 포리스트가 된다.
간선 자체를 우선순위로 삼는 방식이므로, 정점에서 출발해 연결을 확장하는 Prim 알고리즘과 접근 방식이 다르다.
Union-Find로 사이클을 판별하는 방식
간선을 추가하려는 두 정점이 이미 같은 연결 집합에 속한다면, 그 간선은 사이클을 만든다. Kruskal 알고리즘에서는 Union-Find(Disjoint Set) 자료구조로 이 상태를 추적한다.
- Find 연산은 정점이 속한 집합의 대표 원소를 찾는다.
- Union 연산은 서로 다른 두 집합을 하나로 합친다.
두 정점에 Find를 수행했을 때 대표 원소가 다르면 간선을 채택하고 Union을 수행한다. 대표 원소가 같다면 이미 연결된 경로가 있으므로 해당 간선은 제외한다.
의사 코드로 보는 처리 구조
KRUSKAL(G):
A = ∅ // 결과 집합 초기화
모든 정점에 대해 Make-Set 수행
G의 모든 간선을 가중치 기준 오름차순 정렬
FOR 정렬된 각 간선 (u, v):
IF FIND-SET(u) ≠ FIND-SET(v):
A = A ∪ {(u, v)}
UNION(u, v)
RETURN A예제 그래프에서 선택되는 간선
다음 그래프를 가정한다.
간선을 정렬하면 (B-D,2), (D-E,5), (C-D,6), (A-B,7), (A-C,8), (C-E,9), (B-C,11) 순서가 된다.
(B-D,2), (D-E,5), (C-D,6), (A-B,7)은 서로 다른 집합을 연결하므로 선택된다. 이후 (A-C,8), (C-E,9), (B-C,11)은 연결하면 사이클을 만들기 때문에 제외한다.
최종 MST는 다음 간선으로 구성된다.
Python 구현
입력 정점은 0..n-1 인덱스를 사용하며, edges = [(u, v, w), ...] 형식의 무방향 그래프를 가정한다. 반환값은 (total_cost, mst_edges)이고, 비연결 입력에서는 최소 신장 포리스트를 반환한다.
# kruskal.py
from typing import List, Tuple
class DSU:
def __init__(self, n: int):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x: int) -> int:
while x != self.parent[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.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
def kruskal(n: int, edges: List[Tuple[int, int, float]]):
# 자기 루프 제거
edges = [(u, v, w) for (u, v, w) in edges if u != v]
# 간선 정렬
edges.sort(key=lambda x: x[2])
dsu = DSU(n)
mst_edges: List[Tuple[int, int, float]] = []
total_cost = 0.0
for u, v, w in edges:
if dsu.union(u, v):
mst_edges.append((u, v, w))
total_cost += w
if len(mst_edges) == n - 1: # 연결 그래프이면 조기 종료
break
# 비연결 그래프면 포리스트 반환(간선 수 < n-1)
return total_cost, mst_edges
if __name__ == "__main__":
# 예시: n=5, 간선 목록
n = 5
edges = [
(0, 1, 4), (0, 2, 1), (1, 2, 2),
(1, 3, 5), (2, 3, 8), (2, 4, 10),
(3, 4, 2)
]
cost, tree = kruskal(n, edges)
print("총 비용:", cost)
print("선택 간선:", tree)구현을 검증할 때는 자기 루프가 필터링되는지, 동일 비용 간선의 순서가 달라져도 총 비용이 유지되는지 확인한다. 비연결 그래프에서는 len(mst_edges) < n-1인지와 연결 성분별 커버리지를 함께 점검한다.
정렬 비용이 전체 복잡도를 좌우한다
간선 정렬에는 O(E log E)가 필요하다. 경로 압축과 랭크 최적화를 적용한 Union-Find 연산은 O(E log V)이며, 전체 알고리즘은 O(E log E) 또는 O(E log V)로 표현할 수 있다.
여기서 E는 간선 수, V는 정점 수다. E < V²이므로 O(E log E) = O(E log V²) = O(2E log V) = O(E log V) 관계가 성립한다.
그래프 밀도에 따른 Prim과의 선택
Kruskal은 간선 중심 접근법이라 희소 그래프(sparse graph)에 효율적이다. 반면 Prim은 정점 중심 접근법으로 밀집 그래프(dense graph)에 효율적이다.
Kruskal은 간선 정렬에 더 많은 시간이 들고 Union-Find가 필요하다. Prim은 우선순위 큐 연산 비중이 크며, 우선순위 큐를 사용한다. 그래프의 간선 분포와 구현 환경을 함께 보고 선택해야 한다.
연결 비용을 줄여야 하는 설계 문제
통신망에서는 기지국을 최소 비용으로 모두 연결하기 위해 각 연결 비용을 간선 가중치로 둘 수 있다. 설계에 따라 10~40% 링크 비용 절감을 기대할 수 있다. 도시 간 거리나 도로 건설 비용을 가중치로 둔 도로 네트워크 설계도 같은 구조를 갖는다.
배관 시스템에서는 여러 지점을 연결하는 파이프 설치 비용을 줄이는 데 활용할 수 있다. 전자 회로에서는 필요한 전선 사용을 최소화하는 문제로 연결된다.
구현에서 확인할 부분
Union-Find에는 경로 압축(Path Compression)과 랭크(Rank)를 이용한 Union 최적화를 적용할 수 있다. 대규모 그래프에서는 간선 정보 저장 구조와 메모리 관리도 함께 검토해야 한다.
데이터 규모가 커질 경우 병렬 알고리즘 적용 가능성도 고려 대상이다. Kruskal 알고리즘은 간선 가중치 정렬과 사이클 검사라는 단순한 기준으로 최소 신장 트리 또는 최소 신장 포리스트를 구성하며, 특히 희소 그래프와 네트워크 설계 문제에서 실용적인 선택지가 된다.