크루스칼(Kruskal) 알고리즘은 가중치 그래프에서 최소 신장 트리(MST) 를 구하는 그리디 알고리즘이다. 간선을 가중치 순으로 정렬한 뒤, 사이클을 형성하지 않는 간선을 선택해 MST를 완성한다. 유니온-파인드 자료구조와 결합해 효율적으로 구현한다.
동작 원리
간선 정렬: [(1,2,1), (3,4,2), (2,4,3), (1,3,4), (2,3,5)]
(u, v, 가중치)
1. (1,2,1) 선택 → 사이클 없음 → MST에 추가
2. (3,4,2) 선택 → 사이클 없음 → 추가
3. (2,4,3) 선택 → 사이클 없음 → 추가
4. (1,3,4) 선택 → 사이클 없음 → 추가 → V-1개 완성!
구현
python
def kruskal(n, edges):
# 간선 정렬
edges.sort(key=lambda x: x[2])
parent = list(range(n + 1))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py: return False
parent[px] = py
return True
mst_cost = 0
for u, v, w in edges:
if union(u, v):
mst_cost += w
return mst_cost
edges = [(1,2,1),(3,4,2),(2,4,3),(1,3,4),(2,3,5)]
print(kruskal(4, edges)) # 10
관련 개념
- •유니온-파인드 — 사이클 검사 핵심 도구
- •그래프 — MST의 적용 대상
- •그리디 알고리즘 — 크루스칼의 설계 기법
참고문헌
- •Kruskal, J.B. (1956). On the Shortest Spanning Subtree of a Graph
