단원 26 — 최소 신장 트리 (Minimum Spanning Tree)

1. 모든 간선을 가중치 오름차순 정렬      O(E log E)
2. 각 정점을 독립적인 집합으로 초기화    O(V)
3. 정렬된 간선을 순서대로 처리:
   - 두 끝점이 다른 집합이면:
     → 간선을 MST에 추가 (Union)
     → V-1개 간선이 추가되면 종료
   - 같은 집합이면 사이클 형성 → 건너뜀

시간: O(E log E) + O(E α(V)) ≈ O(E log E)
공간: O(V + E)

1. 임의의 출발 정점을 MST에 추가
2. MST에 인접한 미선택 간선 중 최소 가중치 간선 선택
3. 선택된 정점을 MST에 추가
4. V-1 개 간선이 추가될 때까지 반복

시간: O((V+E) log V)  — heapq 구현
공간: O(V + E)

경로 압축 (Path Compression):
    find(x): 루트를 찾으면서 x의 부모를 루트로 직접 연결
    → 이후 find 연산 O(1) 에 가까워짐

랭크에 의한 합치기 (Union by Rank):
    union(x, y): 랭크(트리 높이 추정)가 낮은 트리를 높은 트리 아래로 합침
    → 트리 높이 O(log V) 보장

상각 복잡도: O(α(V)) ≈ O(1)  (α는 역아커만 함수)

그래프 (무방향):
  1 ──4── 2 ──2── 4
  │      / \      │
  3    1    3     6
  │  /       \    │
  3 ────5──── 5──7──6

간선 정렬:
  (2,3): 1  (1,3): 3  (2,4): 2  (2,5): 3  (1,2): 4  (3,5): 5  (4,5): 6  (5,6): 7

단계:
┌─────┬───────┬─────────────────┬──────────────────┐
│ 순서 │ 간선  │ 같은 집합?      │ MST 간선         │
├─────┼───────┼─────────────────┼──────────────────┤
│  1  │ 2-3:1 │ 아니오 → 추가   │ {2-3}            │
│  2  │ 2-4:2 │ 아니오 → 추가   │ {2-3, 2-4}       │
│  3  │ 1-3:3 │ 아니오 → 추가   │ {2-3, 2-4, 1-3}  │
│  4  │ 2-5:3 │ 아니오 → 추가   │ {… , 2-5}        │
│  5  │ 1-2:4 │ 예 (사이클) → 스킵│ 변화없음         │
│  6  │ 3-5:5 │ 예 (사이클) → 스킵│ 변화없음         │
│  7  │ 5-6:7 │ 아니오 → 추가   │ {… , 5-6} V-1=5개│
└─────┴───────┴─────────────────┴──────────────────┘
MST 총 가중치: 1+2+3+3+7 = 16

python src/01_union_find.py
python src/02_kruskal.py
python src/03_prim.py
python src/04_mst_applications.py

MST 알고리즘 요약
━━━━━━━━━━━━━━━━━━━━━
Kruskal : O(E log E), Union-Find, 희소 그래프
Prim    : O((V+E) log V), heapq, 밀집 그래프
조건    : 가중치 연결 무방향 그래프
성질    : 절단 성질, 사이클 성질
응용    : 네트워크 설계, 클러스터링, 두 번째 MST