크루스칼 알고리즘

크루스칼 알고리즘은 그래프의 최소 신장 트리를 찾기 위한 방법으로,
간선을 중심으로 접근함
모든 간선을 가중치에 따라 정렬한 후,
가장 작은 가중치의 간선부터 선택하여 신장 트리를 형성함

알고리즘 단계

1.간선 정렬

그래프의 모든 간선을
가중치 기준으로 오름차순 정렬

2.초기화

각 정점을 별도의 집합으로 초기화

3.간선 선택

정렬된 간선 리스트에서 가장 작은 간선을 선택
이 간선이 두 개의 서로 다른 집합을 연결할 경우,
그 간선을 신장 트리에 추가

4.집합 병합

선택한 간선의 두 정점을 포함하는 집합을 합친다

5.반복

모든 정점이 포함될 때까지
3번과 4번 과정을 반복

시간 복잡도

크루스칼 알고리즘의 시간 복잡도는
𝑂(𝐸log⁡𝐸)
𝐸 간선의 수

크루스칼 알고리즘이 효과적인 문제 유형

희소 그래프

간선 리스트 중심의 문제

프림 알고리즘과의 차이점

프림 알고리즘과 크루스칼 알고리즘은
모두 최소 신장 트리를 찾기 위한 알고리즘이지만,
접근 방식에서 큰 차이점이 있음

1. 접근 방식

프림 알고리즘
정점 중심의 접근 방식
초기 정점에서 시작하여
인접한 정점들 중에서
최소 가중치의 간선을 선택하면서
신장 트리를 확장해 나감
크루스칼 알고리즘
간선 중심의 접근 방식
모든 간선을 가중치 순으로 정렬한 후,
가장 작은 간선부터 선택하여 신장 트리를 구성

2. 데이터 구조

프림 알고리즘

주로 힙(우선순위 큐)을 사용하여
현재 신장 트리에 포함된 정점과 인접한 간선의 가중치를 관리

크루스칼 알고리즘

유니온-파인드 자료구조를 사용하여
간선을 선택할 때 사이클을 방지하고 집합을 관리

유니온-파인드 자료구조
서로소 집합을 관리하는데 사용되는 자료구조로,
주로 집합의 합치기와
특정 원소의 집합을 찾는 작업을 효율적으로 수행할 수 있도록 설계됨

3. 그래프의 형태

프림 알고리즘

밀집 그래프에서 효율적
많은 간선이 있을 때
빠르게 최소 신장 트리를 찾을 수 있음

밀집 그래프
노드 수가 많을 때
간선 수가 상대적으로 많은 그래프

크루스칼 알고리즘

희소 그래프에서 더 효과적
간선 리스트가 주어졌을 때 유리하게 작용

희소 그래프
노드 수에 비해 간선 수가 상대적으로 적은 그래프

4. 동작 방식

프림 알고리즘
하나의 정점에서 시작하여
점진적으로 신장 트리를 확장

크루스칼 알고리즘
모든 간선을 정렬한 후,
선택 가능한 간선을 하나씩 추가하여
신장 트리를 구성