[Python] 크루스칼 알고리즘(Kruskal MST Algorithm)

정의

• 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용
• 탐욕적인 방법(Greedy method)을 이용해 모든 정점을 최소 비용으로 연결하는 최적의 해를 구하는 것
• 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택
• 이전 단계에서 만들어진 신장 트리와 상관 없이 무조건 최소 간선만을 선택

구현

1. 그래프의 간선들의 가중치를 기준으로 오름차순으로 정렬
2. 정렬된 간선 리스트에서 순서대로 사이클을 생성하지 않는 간선 선택
   1. 가장 낮은 가중치의 간선 선택
   2. 사이클이 발생하는 경우 해당 간선은 제외
      (Union-Find 알고리즘을 통해 사이클 존재 여부 파악 가능)
3. 해당 간선을 현재의 MST의 집합에 추가

'''
test case
5
8
C D 1
A B 9
A C 3
A E 7
B D 11
A D 20
B C 14
C E 5
'''

k = int(input()) # 정점의 갯수
n = int(input()) # 간선의 갯수
lst = [list(input().split()) for _ in range(n)]
lst.sort(key=lambda x:int(x[2])) 
costs = 0
arr = [0]*k

def union(a, b):
    global arr
    fa, fb = find(a), find(b)
    if fa == fb: return False # 사이클이 존재하는 경우
    arr[ord(fb)-65] = fa
    return True

def find(x):
    global arr
    if arr[ord(x)-65] == 0:
        return x
    ret = find(arr[ord(x)-65])
    arr[ord(x)-65] = ret
    return ret

for i in range(n):
    a, b, cost = lst[i]
    if union(a, b):
        costs += int(cost)
print(costs)

참고

참고2