크루스칼 알고리즘 - 비방향성 그래프의 최소 비용 신장트리 (MST)

참고 교재

이것이 코딩테스트다 with 파이썬 (나동빈, 2021)

---

알고리즘 분류

그래프 알고리즘, 비방향성 그래프, 최소 비용 신장트리(MST)

선행 알고리즘

유니온 파인드 알고리즘

정의

신장 트리 중에서 최소 비용으로 만들 수 있는 최소 신장 트리를 찾는 알고리즘

절차

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

코드

def init_parent(parent, n):
    for i in range(n):
        parent[i] = i

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
        return parent[x]

    return 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

v, e = map(int, input().split())  # v: 정점의 개수, e: 간선의 개수
edges = []
parent = [0] * (v + 1)  # 인덱스 1부터 시작한다고 가정
result = 0

for i in range(e):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))

edges.sort()

init_parent(parent, v + 1)

for (cost, a, b) in edges:
    # 사이클이 발생하지 않는 경우만 간선에 포함
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost

print(result)