[Python] 크루스칼 알고리즘 / MST / 최소 신장 트리

🔎 크루스칼 알고리즘이란?

대표적인 최소 신장 트리 알고리즘이다.

그리디 알고리즘으로 분류된다.

신장트리란?
그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프이다.

최소신장트리란?
하나의 그래프에서 많은 신장트리 중에 최소한의 비용으로 구성된 신장트리이다.

동작 과정

1. 간선 데이터를 비용에 따라 오름차순 정렬

2. 간선을 하나씩 확인하면서 현재의 간선이 사이클을 발생시키는지 확인

    사이클 발생 O > 최소 신장 트리에 포함 X

    사이클 발생 X > 최소 신장 트리에 포함 O

3. 모든 간선에 대하여 2를 반복

 

cost 가 낮은 edge 부터 차례대로 사이클이 발생하는지 확인합니다.

이때 union-find 가 활용되는데  아래 게시물을 참고해주세요.

2023.06.16 - [algorithm/개념] - [Python] Union - Find 유니온 파인드/서로소 집합

[Python] Union - Find 유니온 파인드/서로소 집합

크루스칼 알고리즘은 edge 의 개수가 E 개 일 때 O(ElogE) 의 시간복잡도를 가진다.

 

📋 example)

step 1 (cost가 제일 낮은 edge) 부터 차례대로 확인하기

사이클이 발생하지 않는 경우만 집합에 포함

    사이클 발생 O > 최소 신장 트리에 포함 X       는 회색 표시

    사이클 발생 X > 최소 신장 트리에 포함 O

📜 code

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

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

# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().spli t())
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_parent(parent, a) != find_parent(parent, b):
        union(parent, a, b)
        result += cost

print(result)

 

 

참고)

https://www.youtube.com/watch?v=aOhhNFTIeFI&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=8