신장트리(SpanningTree)그래프 중 모든 정점이 간선으로 연결되어 있고, 간선들 사이에 사이클이 없는 그래프를 의미한다. 특징으로는 N개의 정점을 가지는 그래프의 최소 간선(edge)의 수는 (N-1)개이다. 최소 비용 신장 트리 (MST, Minimum SpanningTree)신장 트리는 그래프에서 모든 정점에 대한 최소한의 연결만을 남긴 그래프이다. 한 곳으로 도달하는 경우가 두 개 이상 존재하는 경우, 즉 사이클이 존재하는 경우에는 최소한의 연결이라 말할 수 없기 때문에, 모든 위치 하나에서 다른 곳으로 이동하는 경우는 단 한 가지로 결정되도록 항상 트리의 형태를 나타낸다. 최소 비용 신장 트리는 이러한 신장 트리들 중 간선의 가중치 합이 가장 작은 트리이다. 최소 비용 신장 트리는 그리디 ..