MST

MST(최소 신장 트리)를 구할때는 그리디 알고리즘 사용(크루스칼, 프림)
최단 경로 트리를 구하는 다익스트라 알고리즘과 다르다.

크루스칼 알고리즘
- 가중치가 최소인 가선을 하나씩 선택하면서 신장트리를 만드느 알고리즘
1. 모든 간선을 가중치에 따라 오름차순으로 정렬
2. 가중치가 가장 낮은 간선부터 차례대로 선택하면서 트리를 구성
 -> 간선에 사이클이 존재 시 다음 간선으로 넘어간다.
3. n-1 개의 간선이 선택될 때 까지 2번을 반복

프림 알고리즘
- 지금까지 연결된 정점에서 연결된 간선들 중 하나씩 선택하며 MST를 만들어 가는 방식
1. 임의 정점 하나에서 시작
2. 선택한 정점과 인접한 정점들 중의 가중치가 최소인 간선을 선택 후 이어진 정점의 집합에 포함
3. 모든 정점이 다 선택될 때 까지 2번 과정을 반복