[알고리즘] 최소 신장 트리 (MST)

최소 신장 트리 (MST)

신장 트리 (Spanning Tree)

✔ 그래프 내의 모든 정점을 포함하는 트리
✔ 그래프의 최소 연결 부분 그래프 (N - 1)개의 간선 -> 트리 형태

최소 신장 트리 (Minimum spanning Tree)

✔ Spanning Tree 중에서 간선의 가중치 합이 최소(Minimun)인 트리

✔ 최소 신장 트리는 여러 개 일 수 있다.

MST 구현 - 크루스칼 알고리즘

✔ Greedy를 이용해 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택한다.

동작 순서

1. 간선을 오름차순으로 정렬한다. (최소 비용)
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
   (Union - Find 이용: Union-Find 알고리즘이란?!)
3. 선택한 간선을 현재 MST집합에 추가한다.

소스 코드

# V: 정점 개수, E: 간선 개수
V, E = map(int, input().split())
# parent: 부모 테이블 (자기 자신으로 초기화)
parent = [i  for  i  in  range(V + 1)]


# find 함수
def  find(x):
	if  parent[x] != x:
		parent[x] = find(parent[x])
	return  parent[x]
   
   
# union 함수
def  merge(x, y):
	x = find(x)
	y = find(y)
	
	if  x < y:
		parent[y] = x
	else:
		parent[x] = y

	return


# edges: 간선 정보를 담을 리스트, total_cost: 최소 신장 트리의 가중치 합계
edges = []
total_cost = 0

# 간선 정보 입력
for  _  in  range(E):
	node1, node2, cost = map(int, input().split())
	edges.append((cost, node1, node2))  

# 가중치 기준으로 정렬
edges.sort()
   
# 각 간선에 대해 유니온-파인드로 cylce 여부 판단하여 크루스칼 알고리즘 수행
for  i  in  range(E):
	cost, node1, node2 = edges[i]
	# 부모 노드가 다르면 cylce하지 않다
	if  find(node1) != find(node2):
		# mst에 포함
		merge(node1, node2)
		# 가중치 계산
		total_cost += cost  

# 가중치 합계 출력
print(total_cost)