최소 신장 트리 - 크루스칼 알고리즘

크루스칼 알고리즘

1. 간선 데이터를 비용 오름차순으로 정렬한다.
2. 모든 간선을 하나씩 확인하며 사이클을 발생시키는지 확인한다.
   1. 사이클이 발생하지 않으면 최소 신장 트리에 포함시킨다.
   2. 사이클이 발생하는 경우 포함시키지 않는다.

대표 예제

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
    

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_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost
print(result)

input

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

output
159