Kruskal: 간선을 정렬해 그리디하게 선택하는 최소 신장 트리
Kruskal 알고리즘은 그래프의 모든 간선을 가중치 기준으로 정렬한 뒤, 사이클을 만들지 않는 간선만 순서대로 선택해서 최소 신장 트리(MST, Minimum Spanning Tree)를 구성하는 그리디(greedy) 알고리즘이다. 사이클 판별에는 합집합 찾기(Union-Find, Disjoint Set Union) 자료구조를 사용한다. 정점 수보다 간선
1. 개념
Kruskal 알고리즘은 가중치가 있는 무방향 연결 그래프에서 모든 정점을 연결하면서 간선 가중치의 합이 최소가 되는 부분 그래프인 최소 신장 트리(MST)를 찾는 알고리즘이다.
신장 트리(spanning tree)는 그래프의 모든 정점을 포함하면서 사이클이 없는 부분 그래프를 말한다. 정점이 V개면 신장 트리의 간선 수는 항상 V-1개다. Kruskal은 이 신장 트리 중 가중치 합이 최소인 것을 그리디하게 찾는다.
2. 왜 사용하는가
네트워크에서 모든 노드를 연결하되 비용(케이블 길이, 통신 비용, 거리 등)을 최소화해야 하는 문제는 실무에서 자주 등장한다. 전체 간선을 다 놓는 대신 필요한 최소한의 간선만 골라 연결성을 유지하면서 비용을 줄이는 것이 핵심이다.
Prim 알고리즘도 같은 목적을 달성하지만, Prim은 하나의 정점에서 점진적으로 트리를 확장하는 방식이라 우선순위 큐(priority queue)와 인접 리스트 기반 구현이 필요하다. Kruskal은 전체 간선을 정렬해두고 독립적으로 선택 여부를 판단하기 때문에, 간선 리스트만 있어도 구현이 가능하고 희소 그래프에서 유리하다.
3. 동작 원리
- 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다.
- 각 정점을 자기 자신을 부모로 하는 독립된 집합으로 초기화한다(Union-Find 초기화).
- 정렬된 간선을 하나씩 확인한다.
- 간선의 두 정점이 서로 다른 집합에 속해 있다면(사이클이 생기지 않는다면) 그 간선을 MST에 포함하고 두 집합을 합친다(union). - 두 정점이 이미 같은 집합에 속해 있다면(사이클이 생긴다면) 그 간선은 버린다.
- 선택된 간선 수가 V-1개가 되면 종료한다.
사이클 판별을 빠르게 하기 위해 경로 압축(path compression)과 랭크 기반 합치기(union by rank)를 적용한 Union-Find를 사용한다. 이 두 최적화를 함께 쓰면 각 연산의 상각 시간복잡도(amortized time complexity)는 역 아커만 함수(inverse Ackermann function) 기준 O(α(V))로, 실질적으로 상수 시간에 가깝다.
4. 코드 예제
class UnionFind:
def __init__(self, n: int):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x: int) -> int:
# 경로 압축: 탐색 경로상의 노드를 루트에 직접 연결
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x: int, y: int) -> bool:
root_x, root_y = self.find(x), self.find(y)
if root_x == root_y:
return False # 이미 같은 집합 -> 사이클 발생
# 랭크 기반 합치기: 트리 높이를 낮게 유지
if self.rank[root_x] < self.rank[root_y]:
root_x, root_y = root_y, root_x
self.parent[root_y] = root_x
if self.rank[root_x] == self.rank[root_y]:
self.rank[root_x] += 1
return True
def kruskal(n: int, edges: list[tuple[int, int, int]]) -> tuple[int, list[tuple[int, int, int]]]:
"""
n: 정점 개수 (0 ~ n-1)
edges: (가중치, 정점1, 정점2) 튜플 리스트
반환값: (MST 총 가중치, 선택된 간선 리스트)
"""
edges_sorted = sorted(edges, key=lambda e: e[0])
uf = UnionFind(n)
total_weight = 0
mst_edges = []
for weight, u, v in edges_sorted:
if uf.union(u, v):
total_weight += weight
mst_edges.append((u, v, weight))
if len(mst_edges) == n - 1:
break
return total_weight, mst_edges
if __name__ == "__main__":
# 정점: 0,1,2,3,4 / 간선: (가중치, u, v)
edges = [
(2, 0, 1),
(3, 0, 3),
(1, 1, 3),
(4, 1, 2),
(2, 2, 3),
(5, 2, 4),
(3, 3, 4),
]
total, mst = kruskal(5, edges)
print(f"MST 총 가중치: {total}")
print(f"선택된 간선: {mst}")
# MST 총 가중치: 8
# 선택된 간선: [(1, 3, 1), (0, 1, 2), (2, 3, 2), (3, 4, 3)]5. 시간 복잡도 또는 성능 특성
- 간선 정렬: O(E log E)
- Union-Find 연산: 경로 압축 + 랭크 기반 합치기를 함께 적용하면 find/union 각각 상각 O(α(V)) (역 아커만 함수, 실질적으로 상수에 가까움)
- 전체 시간복잡도: O(E log E)
간선 정렬이 전체 실행 시간을 지배한다. E ≤ V²이므로 log E ≤ 2 log V이기 때문에 O(E log E)와 O(E log V)는 같은 차수로 취급하는 경우도 있으나, 정렬 자체가 O(E log E)이므로 이 표기가 더 정확하다.
- 공간 복잡도: O(V + E) — Union-Find 배열 O(V), 간선 리스트 O(E)
6. 실무 사용 사례
- 네트워크 설계: 여러 지점을 케이블이나 광섬유로 연결할 때 총 설치 비용을 최소화하는 배선 설계
- 클러스터링: 단일 연결(single-linkage) 계층적 클러스터링에서 MST를 구성한 뒤 가장 큰 K-1개 간선을 제거해 K개 클러스터를 만드는 방식
- 근사 알고리즘: 외판원 문제(TSP)의 2-근사 알고리즘에서 MST를 기반으로 해를 구성
- 이미지 분할(image segmentation): 픽셀을 정점으로 보고 유사도를 가중치로 하는 그래프 기반 분할 알고리즘
7. 주의할 점
- 그래프가 연결되어 있지 않으면(disconnected) Kruskal은 각 연결 요소마다 신장 트리를 만드는 최소 신장 포레스트(minimum spanning forest)를 반환한다. 실행 전 연결성 가정을 확인해야 한다.
- 음수 가중치가 있어도 Kruskal은 정상 동작한다. 다익스트라(Dijkstra)와 달리 그리디 선택 기준이 사이클 방지이기 때문에 음수 가중치 자체는 문제가 되지 않는다.
- Union-Find를 경로 압축과 랭크 없이 구현하면 최악의 경우 트리가 한쪽으로 길게 늘어져 find 연산이 O(V)까지 걸릴 수 있으므로 반드시 두 최적화를 함께 적용해야 한다.
- 동일한 가중치를 가진 간선이 여러 개 있으면 MST가 유일하지 않을 수 있다(선택 순서에 따라 다른 MST가 나올 수 있으나 총 가중치는 동일).
8. 핵심 정리
Kruskal은 간선을 가중치 순으로 정렬하고 Union-Find로 사이클 여부를 판단하며 그리디하게 MST를 구성하는 알고리즘이다. 시간복잡도는 정렬이 지배하는 O(E log E)이며, 경로 압축과 랭크 기반 합치기를 적용한 Union-Find는 상각 O(α(V))로 동작해 사이클 검사 비용을 거의 무시할 수 있는 수준으로 낮춘다. 간선 리스트만으로 구현할 수 있어 희소 그래프나 간선이 미리 정렬된 형태로 주어지는 문제에서 Prim보다 다루기 쉽다.