크래프톤 정글 주제별 탐구 -MST-

정의

MST(Minimum Spanning Tree: 최소 비용 신장 트리)란, 신장 트리들 중 가장 최소한의 비용 및 가중치의 합이 가장 작은 트리를 뜻한다.

신장 트리란, 그래프에서 모든 정점에 대한 최소한의 연결만을 남긴 그래프이다.

도입

일반적으로 MST를 구하는 몇가지 알고리즘이 존재한다.

1. 그리디 알고리즘

2. 크루스칼 알고리즘

3. 프림 알고리즘