정의

크루스칼은 '가장 저렴한 케이블부터' 선택하여 모든 도시를 연결하는 알고리즘입니다. 사이클만 안 생기면 OK!

핵심 특성

• ✓그리디(Greedy): 매번 가장 저렴한 간선 선택
• ✓Union-Find로 사이클 O(α(n))에 판단
• ✓희소 그래프(E << V²)에서 효율적
• ✓O(E log E) 시간복잡도

시간 복잡도