Spanning Tree 그래프 내의 모든 정점을 포함하면서 순환이 존재하지 않는 간선을 최소로 하는 최소 연결 부분 그래프를 의미합니다. [간선의 수: n-1개, Cycle 존재 X] Minimum Spanning Tree (MST) 특정 그래프의 Spanning Tree 중에서 간선들의 가중치의 합이 최소가 되는 Spanning Tree를 말합니다. MST를 만드는 알고리즘은 대표적으로 크루스칼(Kruskal), 프림(Prim) 두 가지가 있습니다. 크루스칼 알고리즘 모든 간선을 가중치 기준으로 오름차순으로 정렬하고, 이 간선들을 순서대로 모든 정점이 연결될 때까지 연결하는 것입니다. 이 때 서로소 집합(disjoint set) 자료구조의 Union, Find 연산을 사용하여 순환(Cycle) 이 형..
