Time and Space Complexity

시간 복잡도:

• E개의 간선을 정렬하는 것은 O(E log E)입니다. 경로 압축(path compression)을 사용한 각 union-find 연산은 거의 O(1)에 가까우므로, 전형적인 Kruskal 알고리즘은 O(E log E)입니다. 여기서 우리가 구현한 최소 선택 버전은 O(E²)이며, 이는 작은 그래프에서 적합합니다.

공간 복잡도:

• parent 배열을 위해 O(V)가 필요합니다 (입력 간선 제외).

요약:

• Kruskal 알고리즘은 사이클을 확인하기 위해 union-find를 사용하며, 매 단계에서 사이클을 형성하지 않는 가장 저렴한 간선을 추가하여 MST를 확장합니다.
• 모든 MST는 동일한 총 가중치를 공유하므로, 결과값은 유일합니다.