최소 스패닝 트리 - 크루스칼 알고리즘[파이썬 코드]

최소 스패닝 트리, 혹은 최소 신장 트리란 트리 형태의 그래프에서 모든 노드를 연결하면서, 그 간선들의 가중치의 합이 최소인 부분 트리를 말한다.

예를 들어 다음과 같은 그래프가 있을때, 최소 신장 트리는 다음과 같다.

최소 스패닝 트리를 구하는 대표적인 알고리즘이 바로 크루스칼 알고리즘이다 $($Kruskal).

크루스칼 알고리즘은 모든 정점을 최소한의 비용으로 연결하기 위한 상황에서 사용된다.

한 정점에서의 최소 비용 간선을 선택하기 때문에 그리디 알고리즘에 기반을 두고 있다.

크루스칼 알고리즘 수행과정

1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 형성하는지 확인한다. a. 사이클을 형성하지 않으면 최소 신장 트리에 포함. b. 사이클을 형성하면 포함시키지 않음.
3. 모든 간선에 대해 2. 번의 과정을 반복한다.

최소 스패닝 트리도 트리 자료구조이기 때문에 부분 트리에 포함되는 간선의 개수 = 노드의 개수 - 1과 같다는 특징이 있다.

위의 수행과정을 간단히 말하면, 가장 짧은 간선$($sort) 부터 차례대로 집합에 추가한다. 단, 만약 추가되는 간섭이 사이클을 발생 시킨다면$($union-find) 해당 간선은 제외한다.

step 1.

첫번째 단계에서는 가장 짧은 간선을 선택한다.

비용이 1인 $($2, 4)가 선택이되고 union함수를 통해서 노드 2와 노드 4를 동일한 집합에 속하도록 만든다.

step 2.

그 다음으로 작은 비용인 $($1, 4)를 선택한다.

현재 노드 1과 노드 4는 같은 집합에 속해있지 않기 때문에, 노드 1과 노드 4에 대하여 union함수를 호출한다.

step 3.

그 다음으로 작은 비용인 $($1, 2)를 선택한다.

이때, 노드 1과 노드 2가 이미 동일한 집합에 포함되어 있기 때문에 $($사이클을 발생시키기 때문에) 신장 트리에 포함될 수 없다. 따라서 union함수를 호출하지 않는다. $($처리되었지만 신장 트리에는 포함되지 않는 간선은 점선처리)

step 4.

그 다음으로 작은 비용인 $($3, 4)를 선택한다.

현재 노드 3과 노드 4는 같은 집합에 속해있지 않기 때문에, 노드 3과 노드 4에 대하여 union함수를 호출한다.

step 5.

그 다음으로 작은 비용인 $($4, 5)를 선택한다.

현재 노드 4과 노드 5는 같은 집합에 속해있지 않기 때문에, 노드 4과 노드 5에 대하여 union함수를 호출한다.

step 6.

마지막으로 그 다음 작은 비용인 $($1, 3)을 선택한다.

다만, 노드 1과 노드 3은 이미 동일한 집합에 포함되어 있으므로 union함수를 호출하지 않는다.

크루스칼 알고리즘 $($Python)

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

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

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

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

# 특정 원소가 속한 집합을 찾는 함수
def find_parent(parent, x):
    # 루트 노드가 아니라면 루트 노드 찾을때 까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        
# 간선을 하나씩 확인하며
for edge in edges:
    cost, a, b = edge
    # 사이클 발생 안하는 경우에만 집합에 포함
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost
        
print(result)

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

간선의 개수가 E개 일때, 간선을 오름차순으로 정렬하는 과정에서 O$($ElogE)의 시간복잡도가 소요된다.

이는 크루스칼 알고리즘에서 시간이 가장 오래걸리는 부분이며 서로소 집합 알고리즘의 시간복잡도는 정렬보다 작아서 무시된다.

따라서 크루스칼 알고리즘의 시간복잡도는 O$($ElogE) 가 된다.