[Python] 크루스칼 알고리즘 baseline

최소신장트리(MST, MinimumSpanningTree)를 구하는 알고리즘 중 하나이다.

하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 없어야하고 간선의 가중치가 최소가 되는 트리를 의미한다.

아래의 그림이 바로 그런 예시다.

 

알고리즘은 대략적으로 다음과 같다.

1. 가장 작은 가중치의 간선 탐색

2. 사이클이 생기지 않는 노드인지 확인

3-1. 사이클이 생긴다면 pass

3-2. 사이클이 생기지 않으면 해당 간선 리스트에 저장

 

아래 코드는 MST의 최소 가중치를 구하는 코드다.

# 특정 원소가 속한 집합 찾기
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

# 노드의 개수와 간선(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())
    # 비용순으로 정렬하기 위해서 cost를 맨 앞으로 배치
    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(parent, a, b)
        result+=cost

print(result)