MST의 조건
- 그래프는 무방향 연결 그래프여야 한다.
- 모든 정점을 포함해야 한다.
- 사이클이 없어야 한다.
- 간선 수는 정점 수보다 하나 작아야 한다. (N개의 정점 → N-1개의 간선)
- 간선 가중치의 총합이 최소여야 한다.
문제 상황을 상상해보자
- 마을 여러 개를 전선으로 연결하려고 해.
- 전선을 설치하는 데는 비용이 들어.
- 모든 마을을 연결하되, 총 비용을 최소로 하고 싶어.
- 이때 가장 저렴한 전선부터 하나씩 연결해나가는 방식이 바로 크루스칼 알고리즘이야.
필요한 준비물: 유니온 파인드 (Disjoint Set)
왜 필요하냐면?
"두 마을(정점)을 전선(간선)으로 연결할 때, 이미 같은 네트워크에 있는지 확인해야 하거든."
같은 네트워크라면 굳이 또 연결하면 사이클이 생기니까!
전체 흐름 정리
1단계. 간선을 가중치 오름차순으로 정렬한다.
→ 가장 싼 전선부터 하나씩 고려하기 위해!
2단계. 모든 정점을 서로 독립된 집합으로 초기화한다.
→ 유니온 파인드를 위한 준비!
3단계. 간선을 하나씩 보면서 다음 작업을 수행한다:
- 두 정점이 같은 집합에 속해 있는가?
- Yes → 사이클 생기니까 무시
- No → 서로 다른 집합이니 연결 O → MST에 추가 + 두 집합을 하나로 합침
4단계. 간선 선택을 N - 1개 할 때까지 반복한다.
→ 정점이 N개라면, 간선은 N - 1개만 있으면 모든 정점이 연결되니까!
유니온 파인드 구조의 핵심 동작
Find(x)→ x가 속한 집합(루트)을 찾음Union(x, y)→ x와 y가 속한 집합을 하나로 합침- 같은 집합이면 사이클 생김 → 제외
예시로 흐름 완벽히 익히기
그래프:
정점: 4개\
간선 (u, v, 비용):
(1, 2, 1)
(1, 3, 3)
(2, 3, 2)
(3, 4, 4)▶ 1단계: 간선 정렬
오름차순으로 정렬하면:
(1, 2, 1)
(2, 3, 2)
(1, 3, 3)
(3, 4, 4)▶ 2단계: 초기 상태
- 각 정점은 자기 자신이 루트
- 집합 상태: [[1], [2], [3], [4]]
▶ 3단계: 간선 하나씩 고려하며 연결
(1, 2, 1)
- Find(1) = 1, Find(2) = 2 → 다름
- Union(1, 2)
- 선택됨 → MST에 포함
- 집합: [[1,2], [3], [4]]
(2, 3, 2)
- Find(2) = 1 (→ 경로 압축으로 루트는 1)
- Find(3) = 3
- 다름 → Union(1, 3)
- 선택됨 → MST에 포함
- 집합: [[1,2,3], [4]]
(1, 3, 3)
- Find(1) = 1, Find(3) = 1 → 같음 → 사이클 생김 → 무시
(3, 4, 4)
- Find(3) = 1, Find(4) = 4 → 다름
- Union(1, 4)
- 선택됨 → MST에 포함
- 집합: [[1,2,3,4]]
MST 간선 수 = 3개 → 끝
최종 결과
선택된 간선:
(1, 2, 1)
(2, 3, 2)
(3, 4, 4)총 비용: 1 + 2 + 4 = 7
시간 복잡도
- 간선 정렬:
O(E log E) - 유니온 파인드 연산:
O(α(N))(거의 상수)
총 시간 복잡도: O(E log E)
상태 흐름 다시 보기
Step 1: 초기 상태
모든 정점은 자기 자신이 루트
1: 1
2: 2
3: 3
4: 4Step 2: 간선 (1, 2, 1) 선택
- Find(1) = 1
- Find(2) = 2 → 서로 다른 집합 → Union(1, 2)
- 보통 작은 쪽(또는 순서대로) 기준으로 합치면, 2의 부모를 1로 설정
- 결과 상태:
1: 1 2: 1 3: 3 4: 4
→ 이제 1과 2는 같은 집합. 3은 여전히 독립된 집합이야!
Step 3: 간선 (2, 3, 2) 선택
Find(2)→ 2의 부모는 1 → 루트는 1Find(3)→ 아직 독립 → 루트는 3
→ 루트가 다르기 때문에 사이클 X → Union(1, 3) 수행
→ 이제 3도 같은 집합으로 합쳐져!
취업 준비생 낚곰입니다!! 반갑습니다!!