트리 : 연결그래프이며 정점의 개수가 N개 일 때, 간선의 개수가 N-1인 트리스패닝트리 : 신장트리, 무향 연결 그래프가 있을 때 그 그래프에서 간선을 부분적으로 뽑아서 만들 수 있는,그래프의 정점 개수와 같은 정점 개수를 가지는 트리최소 스패닝 트리 (MST) : 트리의 간선마다 가중치(cost)가 있을 때, 간선의 가중치 합이 최소인 트리 하나의 그래프에 대해 스패닝 트리는 여러개일 수도 있다.또한 MST도 여러개일 수 있지만, 스패닝 트리 개수 이하이다. MST를 구하는 알고리즘은 프림알고리즘, 크루스칼 알고리즘 등이 있지만,크루스칼 알고리즘이 응용 가능성이 높다. 크루스칼 알고리즘의 작동 방식1. 간선들을 가중치 순으로 오름차순 정렬하고, 정점들을 각 컴포넌트로 초기화한다.2. 간선들을 훑으면서..