최소 신장 트리란?신장 트리(스패닝 트리)란 그래프 내의 모든 정점을 포함하는 트리를 의미한다.트리이므로 간선의 수는 (정점의 수 - 1)이며, 사이클은 존재하지 않는다. 신장 트리 중 가중치의 합이 최소인 트리를 최소 신장 트리라고 한다. 최소 신장 트리 구하기크루스칼 알고리즘(Kruskal's Algorithm)크루스칼 알고리즘은 가중치가 가장 작은 간선부터 확인하며 사이클이 생기지 않는 경우 MST에 포함하는 그리디(Greedy)적인 방법이다. 먼저 그래프 내의 모든 간선을 가중치에 대한 오름차순으로 정렬한다.이후 반복문을 돌며 가중치가 작은 가중치부터 MST에 포함 가능한지 여부를 판별하는데, 서로소 집합을 이용하는 방법이 가장 대중적이다.($A$와 $B$가 이미 같은 집합에 있다면, 이미 해당 ..
