신장 트리 (Spanning Tree)그래프 상의 모든 정점이 사이클 없이 연결된 부분 그래프를 신장 트리라 한다.정점의 개수가 n개인 경우, 신장 트리는 n-1개의 간선을 가진다.최소 비용 신장 트리 (Minimum-cost Spanning Tree, MST)주어진 그래프에서 모든 정점을 연결하는 트리 중 간선 가중치의 합이 최소인 트리 가중치가 있는 무방향 그래프의 신장 트리의 비용은 신장 트리에 있는 간선들의 비용(가중치)의 합이다.신장 트리의 비용이 최소가 되는 트리를 최소 비용 신장 트리(MST)라 한다.MST를 구성하는 데에는 다음의 제한 조건이 있다.그래프 내에 있는 간선만 사용정확하게 n-1개의 간선만 사용사이클을 생성하는 간선은 사용하지 않음MST를 구하기 위해선 대표적으로 세 가지 알고..