[CS기초] 크루스칼 알고리즘(Kruskal’s algorithm)

크루스칼 알고리즘

크루스칼 알고리즘 개요

'하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프'를 신장 트리(Spanning Tree)라 합니다. 이 조건은 트리의 성립 조건과 동일하므로, 해당 그래프를 신장 트리라고 부릅니다.

 

신장 트리 중에서도 가장 적은 비용으로 만들 수 있는 트리를 찾는 알고리즘을 최소 신장 트리 알고리즘이라 하며, 대표적인 예가 크루스칼 알고리즘(Kruskal’s algorithm)입니다.

 

크루스칼 알고리즘을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있는데요. 이 알고리즘은 그리디 알고리즘으로 분류됩니다. 먼저 모든 간선에 대하여 정렬을 수행한 뒤 가장 거리가 짧은 간선부터 집합에 포함시킵니다. 이때 사이클을 발생시키는 간선은 집합에 포함하지 않습니다.

 

구체적인 알고리즘을 살펴보면 다음과 같습니다.

1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
   1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
   2. 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
3. 최소 신장 트리에 V-1개의 간선이 연결될 때까지 2번의 과정을 반복한다.

 

크루스칼 알고리즘의 시간 복잡도

크루스칼 알고리즘은 간선의 개수가 E개일 때, O(ElogE)의 시간 복잡도를 가집니다. 그 이유는 크루스칼 알고리즘에서 시간이 가장 오래 걸리는 부분이 간선을 정렬하는 작업이며, E개의 데이터를 정렬했을 때의 시간 복잡도는 O(ElogE)이기 때문이다. 크루스칼 내부에서 사용되는 서로소 집합 알고리즘의 시간 복잡도는 정렬보다 시간이 적게 걸리므로, 전체 시간 복잡도에 큰 영향을 주지 않습니다.

 

파이썬에서 크루스칼 알고리즘의 구현

# find: 특정 원소가 속한 루트 노드를 찾는 함수 (경로 압축 적용)
def find_parent(x):
    if parent[x] != x:
        parent[x] = find_parent(parent[x])
    return parent[x]

# union: 두 원소가 속한 집합을 합치는 함수 (작은 번호가 부모가 되도록 설정)
def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드 개수와 간선(union 연산)의 개수 입력
v, e = map(int, input().split())
parent = [0] * (v+1)    # 부모 테이블 초기화

# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
total_min_cost = 0

# 부모 테이블 상에서, 부모를 자기 자신으로 초기화
for i in range(1, v+1):
    parent[i] = i

# 모든 간선에 대한 정보 입력
for _ in range(e):
    a, b, c = map(int, input().split())
    # 비용 순으로 정렬하기 위해 튜플의 첫 번째 원소를 비용으로 설정
    edges.append((c, a, b))

# 간선을 비용 순으로 정렬
edges.sort()

count = 0   # 연결된 간선 갯수
# 간선을 하나씩 확인
for cost, a, b in edges:
    # 간선이 v-1 개 연결된 경우 종료
    if count == v-1:
        break
    
    # 사이클이 발생하지 않는 경우 집합에 포함.
    # 연결된 간선 갯수를 1 올리고, 최종 비용에 해당 비용을 추가
    if find_parent(a) != find_parent(b):
        count += 1
        total_min_cost += cost
        union_parent(a, b)

print(total_min_cost)