[Python] 최소 스패닝 트리(MST), 크루스칼 알고리즘 (Kruskal Algorithm)

신장 트리 (Spanning Tree)

하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

N개의 노드로 만드는 스패닝 트리는 N-1개의 노드로 구성되어 있다.

 

유니온 파인드 알고리즘을 활용하여 사이클을 검사할 수 있고,

이를 활용하여 스패닝 트리를 만들 수 있다.

 

이중 최소한의 비용으로 구성된 스패닝 트리를 최소 스패닝 트리 (MST) 라고 한다.

최소 스패닝 트리를 구하는 알고리즘으로 크루스칼, 프림 알고리즘이 있는데 크루스칼 알고리즘을 다뤄보겠다.

 

크루스칼 알고리즘 (Kruskal Algorithm)

핵심 원리

가장 거리가 짧은 간선부터 차례대로 집합에 추가하면 된다. 다만 사이클을 발생시키는 간선은 제외하고 연결한다.

[1] 간선 비용에 따라 오름차순으로 정렬
[2] 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
   [2-1] 사이클이 발생하지 않는 경우 최소 스패닝 트리에 포함시킨다.
   [2-2] 사이클이 발생하는 경우 최소 스패닝 트리에 포함시키지 않는다.
[3] 모든 간선에 대하여 2의 과정을 반복한다.

 

시간 복잡도

간선의 개수가 E개 일때 O(ElogE)

간선을 정렬하는 작업이 가장 오래걸리며, sort()함수의 시간복잡도가 nlogn이기 때문이다.

---

소스 코드 

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


# 두 원소가 속한 집합을 합치기
def union(a, b):
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


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

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

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

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

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

# 간선을 하나씩 확인하며
for edge in edges:
    cost, a, b = edge
    # 사이클이 발생하지 않는 경우에만 집합에 포함
    if find(a) != find(b):
        union(a, b)
        result += cost

print(result)

# 입력
# 7 9 
# 1 2 29
# 1 5 75
# 2 3 35
# 2 6 34
# 3 4 7
# 4 6 23
# 4 7 13
# 5 6 53
# 6 7 25
# 출력
# 159

---

본 게시글은 나동빈 저자의 "이것이 코딩테스트다 with 파이썬" 책 내용을 정리한 것입니다.