최소 신장 트리란?
신장 트리(스패닝 트리)란 그래프 내의 모든 정점을 포함하는 트리를 의미한다.
트리이므로 간선의 수는 (정점의 수 - 1)이며, 사이클은 존재하지 않는다.
신장 트리 중 가중치의 합이 최소인 트리를 최소 신장 트리라고 한다.
최소 신장 트리 구하기
크루스칼 알고리즘(Kruskal's Algorithm)
크루스칼 알고리즘은 가중치가 가장 작은 간선부터 확인하며 사이클이 생기지 않는 경우 MST에 포함하는 그리디(Greedy)적인 방법이다.
먼저 그래프 내의 모든 간선을 가중치에 대한 오름차순으로 정렬한다.
이후 반복문을 돌며 가중치가 작은 가중치부터 MST에 포함 가능한지 여부를 판별하는데, 서로소 집합을 이용하는 방법이 가장 대중적이다.
($A$와 $B$가 이미 같은 집합에 있다면, 이미 해당 간선보다 더 적은 가중치로 둘을 연결했으므로 해당 간선은 MST에 포함될 수 없다.)
구현해보기 (Python)
크루스칼 알고리즘을 이용해 MST의 가중치 합을 구하는 코드이다. (서로소 집합 구현부 등 일부 생략)
edges = []
answer = 0
for _ in range(e):
a, b, cost = map(int, input().split())
edges.append((cost, a, b))
edges.sort()
for cost, a, b in edges:
if find(a) != find(b):
union(a, b)
answer += cost
print(answer)
시간 복잡도
크루스칼 알고리즘의 시간복잡도는 정렬에 의해 $O(Elog_2E)$이다. ($E$는 그래프 내 간선의 총 개수이다.)
프림 알고리즘(Prim's Algorithm)
프림 알고리즘은 크루스칼 알고리즘과는 달리 정점 선택을 기반으로 진행된다.
현재까지 탐색한 정점들 중 최소 간선으로 연결된 정점을 선택해나가는 방법이다. (우선순위 큐를 사용해 빠르게 최소 간선을 구할 수 있다.)
구현해보기 (Python)
프림 알고리즘을 이용해 MST의 가중치 합을 구하는 코드이다. (일부 생략)
import heapq
graph = [[] for _ in range(v)] # 인접 리스트
visited = [False] * v # 방문 확인
answer = 0
for _ in range(e):
a, b, cost = map(int, input().split())
graph[a].append((cost, b))
graph[b].append((cost, a))
visited[0] = True
heap = graph[0]
heapq.heapify(heap)
while heap:
cost, a = heapq.heappop(heap)
if not visited[a]:
visited[a] = True
answer += cost
for n in graph[a]:
_, na = n
if not visited[na]:
heapq.heappush(heap, n)
print(answer)
시간 복잡도
탐색 과정에 $O(Vlog_2V)$, 힙 구성에 $O(Elog_2V)$가 소요되어 총 $O((V + E)log_2V)$의 시간 복잡도를 가진다. ($V$는 그래프 내 정점의 개수이다.)
보통 $E \leq V$이므로 $O(Elog_2V)$로 간단히 표현할 수도 있으나, 이렇게만 표현하면 크루스칼 알고리즘보다 무조건 빠르다고 생각될 수 있어 주의가 필요하다.
보통 $E$가 작은 경우 크루스칼 알고리즘이, 큰 경우 프림 알고리즘이 더 빠르다.
관련 문제 (BOJ)
- [1197] 최소 스패닝 트리: MST의 가중치 합을 구하는 문제
- [1774] 우주신과의 교감: 이미 일부가 연결된 상태에서 MST를 구하는 문제
- [1368] 물대기: 가상의 정점(간선)을 활용해 MST를 구해 답을 도출하는 문제
- [17472] 다리 만들기 2: 먼저 DFS/BFS로 그래프를 구성한 후 MST를 구하는 문제
