[MST] 개요

이번 포스트에서는 MST의 개요에 대해서 알아보자.

 

MST

 

문제 제시

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

 

 

키워드: 모든 집들을 연결, 절약할 수 있는 최대 액수(최소 비용)

 

MST(Minimum Spanning Tree) 개념

먼저 Span이란 교각과 교각 사이의 거리를 말한다. 즉 그래프에서는 정점과 정점을 잊는 무향의 간선을 말하며 이 span의 거리는 일반적으로 가중치를 나타낸다.

span의 개념

Spanning Tree(신장 트리)란 말 그대로 span으로 이뤄진 트리이다. span이니까 간선을 의미한다는걸 알겠고 거기에 tree의 속성이 추가된 것이다. tree란 circle을 이루지 않는 특징이 있다. 따라서 Spanning Tree는 다음과 같이 정의할 수 있다.

N개의 정점으로 이뤄진 무향의 그래프에서 n-1개의 간선으로 이뤄진 트리로 circle이 없으며 부모/자식의 관계는 없다.

노드의 집합에서 Spanning Tree는 여러개가 나올 수 있다. 그 중에서 가중치(간선의 합)가 가장 작은 트리가 MST(최소 신장 트리: Minimul Spanning Tree)이다.

3개의 Spanning Tree 중 MST는 22원짜리

MST는 실 생활에서도 활용도가 매우 높은 알고리즘이다. 사내 네트워크 망 구축 시 최소 구축 비용을 찾는다거나 각 도시를 연결하는 도로를 최소 비용으로 설치하는 등의 상황에서 MST가 필요하다.

 

MST를 구하기 위한 알고리즘

일반적으로 MST는 매우 많은 정점과 이를 잊는 간선으로 구성된 완전 그래프(모든 정점들이 서로 연결된 그래프)이다. 그러다 MST를 구성하는 간선을 찾기 위해 단순 조합을 이용한다면 상당한 시간이 필요하다.

정점이 10개만 되도 간선의 개수는 10*9/2 = 45개가 되고 ST를 구성하려면 9개의 간선을 골라야 하므로 45C9 만 해도 9억 가까운 연산이 필요하다.

이처럼 MST를 구할 때 완탐으로는 처리하기 힘든 경우가 많아 두 개의 검증된 그리드 알고리즘을 활용할 수 있다.

• Kruskal: Union-Find 자료 구조 활용
• Prim: Dijkstra와 유사한 형태의 구조

 

Kruskal vs Prim

이 내용은 Kruskal과 Prim을 구현해보고 나서 보는것이 좋다.

	Kruskal	Prim
알고리즘 특징	간선을 선택하며 MST 구성	그래프를 구성 후 정점을 선택하며 MST 구성
	Union-Find 자료구조 활용	Dijkstra와 유사하게 전개
시간복잡도	O(E*logE)	배열: O(V^2), PQ: O(VlogV)
유리한 경우	간선 정보가 주어질 때	그래프가 주어질 때
	간선이 적을 때	간선이 많을 때

엄밀히 말하면 E*logE < V^2 이므로 Kruskal이 유리하지만 익숙한 것을 사용하자.