최소 신장 트리, Minimum Spanning Tree

최소 연결 부분 그래프

조건

1. 정점 N개를 가지는 그래프에서 (N - 1)개의 간선을 연결해야 한다.
2. 연결한 간선의 가중치 합이 가장 최소가 되는 그래프
3. 모든 정점이 연결되어야 하나, 싸이클이 되면 안된다.

싸이클이 생기는 경우에는 불필요하게 하나의 간선이 연결되었다는 뜻
최소한의 간선으로 연결되는 경우에는 결국 정점의 수와 하나 차이나는 간선이 연결되어야 함

알고리즘

1. 크루스칼(Kruskal) 알고리즘
   간선을 기준으로 구함
2. 프림(Prim) 알고리즘
   정점을 기준으로 구함