먼저 신장 트리에 대해서 알아보자.
신장 트리
그래프 내의 모든 정점을 포함하는 트리
그래프의 최소 연결 부분 그래프로 간선의 수가 가장 적다 (최소 연결이므로). 즉, 그래프에서 일부 간선을 선택해서 만든 트리이다.
따라서 최소 신장 트리는 Spanning Tree중에서 사용된 간선들의 가중치 합이 최소인 트리를 말한다.
** 참고 :*
[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog