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

개요 

• 신장 트리 : 그래프의 모든 정점을 포함하는 트리
• 최소 신장 트리 : 신장 트리들 중 가장 간선들 가중치의 합이 최소인 신장 트리입니다. 가장 큰 특징으로 트리 내 사이클이 존재하지 않습니다. 

 

최소 신장 트리를 찾는 알고리즘 

* Kruskal 

1. 각 간선의 가중치가 낮은 순으로 정렬
2. 가장 가중치가 낮은 간선 순으로 탐색
   1. 해당 간선을 트리에 포함할 때 사이클이 없는 경우 -> 포함
   2. 해당 간선을 트리에 포함할 때 사이클이 있는 경우 -> 제외

 

* Prim

1. 시작 정점에서 이동 가능한 간선 탐색
2. 가장 가중치가 낮은 간선 순으로 탐색
   1. 해당 간선을 트리에 포함할 때 사이클이 없는 경우 -> 포함
   2. 해당 간선을 트리에 포함할 때 사이클이 있는 경우 -> 제외

 

최소 신장 트리 판단을 위해 사용하는 자료구조, 알고리즘

해당 트리가 최소 신장 트리인지 판단하기 위해 Disjoint-set 자료구조 및 Union Find 알고리즘을 활용할 수 있습니다.

* Disjoint-set

서로소 집합

• 서로 같은 원소를 가지지 않는 두개 이상의 집합
• 트리의 사이클 존재 여부 판별에 활용

 

* Union Find

합집합 찾기, 해당 신장 트리가 최소 신장 트리인지 판단하기 위해 트리 내 모든 노드가 다른 트리에 포함되는 지 (== 합집합) 확인하는 방법을 사용합니다. 

• Disjoint-set 에서 합집합을 찾는 알고리즘
• 두 개의 정점이 동일한 집합에 속하는 지 판단할 때 활용

 

참고 자료 

https://www.acmicpc.net/problem/1197

[백준 1197번 / C++ / 크루스칼] 최소 스패닝 트리

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog

크러스컬 알고리즘 - 위키백과, 우리 모두의 백과사전

17. Union-Find(합집합 찾기)