Kruskal 알고리즘

Kruskal 알고리즘

간선을 가중치 오름차순으로 정렬한 후 사이클을 만들지 않는 간선을 선택하여 MST를 구성하는 탐욕 알고리즘

목적: MST, 간선 기반, 희소 그래프

특징: 탐욕, 간선 정렬, 유니온 파인드

동작 상세

Union-Find (서로소 집합) 자료구조

• •MakeSet(x): 각 정점을 자신만의 집합으로 초기화, O(1)
• •Find(x): x가 속한 집합의 대표 원소(루트) 반환
• •Union(x, y): 두 집합 합치기
• •경로 압축 + 랭크 합치기 적용 시: 연산당 O(α(n)), α = 아커만 역함수 ≈ 상수

시간 복잡도: O(E log E) - 간선 정렬이 지배적 + O(E α(V)) ≈ O(E log E) = O(E log V) (∵ E ≤ V²이므로 log E ≤ 2 log V)

공간 복잡도: O(V) - 유니온 파인드 배열 (parent, rank)

장점: 간단한 구현, 희소 그래프에서 효율적(E << V²), 간선 리스트만으로 동작 (그래프 전체 구조 불필요)

단점: 간선 정렬 필요(O(E log E)), 밀집 그래프에서 Prim보다 느림

적용사례: 네트워크 설계(최소 비용 케이블링), 클러스터링, 희소 그래프

비교: Kruskal(간선기반/정렬/희소) vs Prim(정점기반/우선순위큐/밀집)

연관: MST, Prim, 유니온 파인드, 탐욕, 정렬