크루스칼 알고리즘: 싼 간선부터 고르면서 사이클을 막기
크루스칼 알고리즘은 무방향 가중 그래프의 간선을 작은 비용부터 검사하며 최소 신장 트리를 만든다. 양끝이 아직 다른 연결 그룹이면 간선을 선택하고, 같은 그룹이면 사이클을 만들므로 건너뛴다. 처음에는 모든 정점이 각각 하나의 그룹이다.
작은 가중치부터 검토하며 서로 다른 연결 요소를 합치는 간선을 선택한다.
선택 기준에 연결성 검사가 붙는다
간선을 싸다는 이유만으로 모두 고르면 사이클이 생기고 필요 없는 비용을 낸다. 분리 집합은 선택한 간선들로 연결된 그룹을 유지한다. find(u)와 find(v)가 다를 때만 union하여 두 그룹을 잇는다.
다음 코드는 DisjointSet이 경로 압축과 크기 기준 결합을 제공한다고 가정한다. 결과 간선 수로 입력의 연결 여부도 확인한다.
def kruskal(vertex_count, weighted_edges):
groups = DisjointSet(vertex_count)
chosen_edges = []
total_cost = 0
for cost, first, second in sorted(weighted_edges):
if groups.find(first) == groups.find(second):
continue
groups.union(first, second)
chosen_edges.append((first, second, cost))
total_cost += cost
if len(chosen_edges) == vertex_count - 1:
break
connected = vertex_count == 0 or len(chosen_edges) == vertex_count - 1
return chosen_edges, total_cost, connected
빈 그래프를 어떻게 다룰지는 API 정의에 따라 달라질 수 있다. 비연결 입력에서는 chosen_edges가 최소 신장 숲이며 전체를 잇는 트리라고 반환하면 안 된다.
네 정점을 연결하는 과정
A—B=1, B—C=2, A—C=3, C—D=4, B—D=5라면 1과 2를 선택하여 A,B,C를 합친다. 비용 3 간선은 이미 같은 그룹의 A,C를 잇기 때문에 버린다. 비용 4를 선택하여 D를 합치면 세 간선으로 네 정점이 연결되고 총비용은 7이다.
이 시점의 두 그룹을 가르는 컷에서 가장 가벼운 선택 가능한 간선을 고른다는 관점으로 안전성을 설명할 수 있다. 같은 비용이 있으면 어느 것을 먼저 고르는지에 따라 트리 모양은 달라져도 최소 총합은 유지된다.
간선 정렬이 O(E log E), 분리 집합 연산이 전체 O(Eα(V)) 정도이므로 보통 정렬이 지배한다. 간선 목록과 결과를 저장하고 분리 집합에 O(V) 공간이 필요하다. 이미 정렬된 입력처럼 특수 조건이 있다면 비용 구성은 달라진다.
자기 루프는 같은 대표를 잇기 때문에 자동으로 제외되고 평행 간선도 비용과 연결 여부에 따라 처리할 수 있다. 음수 간선은 오름차순에서 먼저 검사하면 된다. 그러나 방향 그래프의 최소 연결 문제에는 이 알고리즘을 그대로 적용할 수 없다.
크루스칼은 전체 간선 목록을 얻기 쉽고 그래프가 희소할 때 직관적이다. 단순한 “싼 것부터 선택”이 아니라 사이클 검사와 컷 성질이 결합된 탐욕 알고리즘이라는 점을 기억해야 한다.