주어진 마을에 여러 집과 이를 연결하는 도로가 있다. 각 도로는 두 개의 집을 연결하며, 도로를 수리하는데 비용 w(u, v)이 소요된다. 목표는 최소 비용으로 필요한 도로만 수리하여 모든 집이 서로 연결되도록 하는 것이다. 이 문제는 MST를 구하는 알고리즘으로 해결할 수 있다.수리할 도로 집합 T⊆E를 찾으며, 이때 T는 모든 정점을 연결하면서 최소 비용을 만족하는 스패닝 트리가 되어야한다. 최소 비용 스패닝 트리(Minimum Spainning Tree)란, 주어진 그래프의 모든 정점을 연결하는 모든 스패닝 트리 중에서 가중치의 합이 최소가 되는 트리를 의미한다. 위 그림에서 두껍게 칠해진 선들의 집합을 MST라고 한다. 모든 노드들을 연결하고 있으며, 도합 37이라는 최소 비용을 가지고 있다.간선..
