최소 신장 트리 (Minimum Spanning Tree, MST)
- 신장 트리(Spanning Tree)는 그래프 내에 있는 모든 정점을 연결하면서, 사이클을 형성하지 않는 트리/그래프 를 말합니다.
- 그리고 최소 신장 트리는 각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장 트리를 말합니다.
- 즉, 신장 트리를 최소한의 값으로 구성하는 경우를 뜻합니다.
- 최소 신장 트리를 구하는 2가지 대표적인 알고리즘이 있는데 프림과 크루스칼 알고리즘입니다.
- 프림 알고리즘은 노드(정점)를 기준으로 최소 신장 트리를 구하는 다익스트라 알고리즘과 유사한 구조의 bfs 알고리즘 입니다.
- 크루스칼 알고리즘은 간선을 기준으로 최소 신장 트리를 구하는 유니온 파인드를 활용하는 알고리즘입니다.
크루스칼 알고리즘
- 우선 주어진 그래프의 가중치를 확인하여, 오름차순으로 정렬합니다.
- 이는 신장 트리를 만들 수 있는 최소 비용을 확인하기 위함입니다.
- 그리고 순차적으로 하나씩 해당 간선을 그래프에 추가했을 때, 싸이클이 생성되는지 확인하는 절차를 거칩니다.
- 유니온 파인드 알고리즘을 이용해서 새로운 간선이 이미 형성된 간선들의 집합(그래프)와 같은 부모를 갖게 된다면 싸이클이 발생하는 것으로 간주할 수 있습니다.
- 싸이클이 발생하지 않는다면, 이 간선을 추가하고 비용을 합산합니다. 그리고 그래프에 추가된 간선의 갯수를 카운트 합니다.
- 그래프를 구성하는 간선의 갯수가 (정점 갯수 - 1) 과 동일해진다면, 신장 트리가 구현된 것입니다.
- 모든 정점을 연결하기 위해서는 (싸이클이 없다는 전제하에) 정점 갯수 - 1 만큼의 간선이 필요합니다.
import sys
import heapq
input = sys.stdin.readline
V, E = map(int, input().split())
parent = [i for i in range(V+1)]
edges = list()
for _ in range(E):
a, b, cost = map(int, input().split())
# cost 가 작은 순으로 방문해야 하므로 최소힙 사용
# 일반 정렬을 사용할 수 있으며, 더 빠름
heapq.heappush(edges, (cost, a, b))
def find(x):
if x == parent[x]:
return x
else:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
_x = find(x)
_y = find(y)
if _x == _y : return False
if _x > _y:
parent[_x] = _y
else:
parent[_y] = _x
return True
total = 0
cnt = 0
while edges:
cost, a, b = heapq.heappop(edges)
result = union(a, b)
# 유니온이 성공하는 경우에, 즉 싸이클이 생기지 않으면 코스트를 합산
if result:
total += cost
cnt += 1
if cnt == V-1: break # 최적화
추천 문제