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

알고리즘 분류

---

• 그래프 알고리즘 (무향 그래프)
• 최소 비용 신장트리(MST)

선행 알고리즘

---

유니온 파인드 알고리즘

알고리즘 코드

---

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


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

    return x


def union(parent, a, b):
    a = find(parent, a)
    b = find(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, a) != find(parent, b):
        union(parent, a, b)
        result += cost

print(result)

설명

---

최소 신장 트리 (Minimum Spanning Tree)

신장 트리 중에서 최소 비용으로 만들 수 있는 트리

절차

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

참고 레퍼런스

---

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