[알고리즘] 최소 신장 트리(MST), 크루스칼 알고리즘(Kruskal Algorithm)

1. 신장 트리(Spannging tree)

• 그래프에서 모든 정점이 서로 연결이 되며 싸이클이 존재하지 않는 그래프
• 신장 트리들 중에서 가중치의 합이 최소가 되는 신장 트리를 최소 신장 트리(Minimum Spanning Tree, MST)라고 함

 

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

• 그리디(Greedy) 알고리즘
• 그래프 내의 모든 정점을 가장 적은 비용으로 연결하기 위해 사용
• 알고리즘 동작 과정
  1. 간선 데이터를 비용(가중치)에 따라 오름차순으로 정렬
  2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
     1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함
     2. 사이클이 발생하는 경우 포함시키지 않음
  3. 모든 간선에 대해 2. 과정 반복

 

def find(parent, i):
    # union find 알고리즘에서 부모 초기값을 자기 자신으로 설정해둠
    if parent[i] == i: 
        return i	# 부모를 찾으면 부모 반환
    return find(parent, parent[i])

def union(parent, rank, x, y):
    xroot = find(parent, x)
    yroot = find(parent, y)
    
    # 더 깊이가 깊은 트리에 짧은 트리를 연결
    if rank[xroot] < rank[yroot]:
        parent[xroot] = yroot
    elif rank[xroot] > rank[yroot]:
        parent[yroot] = xroot
    else:
        parent[yroot] = xroot
        rank[xroot] += 1

def kruskal(graph, V):
    result = []  # 최소 스패닝 트리를 저장할 리스트
    i, e = 0, 0  # 사용된 간선의 수
    graph = sorted(graph, key=lambda item: item[2]) # 비용 기준으로 정렬
    parent = []
    rank = []

    for node in range(V):
        parent.append(node)
        rank.append(0)

    while e < V - 1:
        u, v, w = graph[i]
        i = i + 1
        x = find(parent, u)
        y = find(parent, v)
        if x != y:
            e = e + 1
            result.append(w)
            union(parent, rank, x, y)

    return sum(result)

N, M = map(int, input().split())
graph = []

for _ in range(M):
    a, b, c = map(int, input().split())
    graph.append((a-1, b-1, c))  # 인덱스를 0부터 시작하도록 조정

# 최소 비용 출력
print(kruskal(graph, N))