크루스컬 알고리즘(Kruskal Algorithm) 가중치가 있는 무방향 그래프를 최소 신장 트리로 만드는 알고리즘입니다. 최소 신장 트리는 가중치가 최소인 순환이 없는 무방향 그래프 입니다. 순환이 없으므로 간선 수는 정점 수 - 1이 됩니다. 크루스컬 알고리즘은 Greedy Algorithm에 속하며, 매 번 순환이 되지 않도록 가중치가 가장 적은 다음 간선을 선택합니다. 시잔복잡도 O(ElogN) 작동 원리 (1) 간선을 가중치를 기준으로 정렬합니다. (2) 가장 가중치가 작은 간선(u, v)을 선택합니다. (3) union find 알고리즘을 통해 u와 v를 병합합니다. (4) union find 알고리즘은 각 정점을 분리 집합으로 만들고 서로 다른 집합에 속해있는 정점을 하나의 집합으로 병합합니..