13. 최소 신장 트리 (MST, Minimum Spanning Tree) — Kruskal / Prim

핵심 인사이트 (3줄 요약)

본질: MST (Minimum Spanning Tree, 최소 신장 트리)는 가중치 연결 무방향 그래프에서 모든 정점을 연결하되 간선 가중치 합이 최소인 사이클 없는 부분 그래프다.

가치: 네트워크 설계, 클러스터링, 근사 TSP 등 "최소 비용으로 모두 연결" 문제를 O(E log E) 또는 O(E log V) 에 해결하는 탐욕 알고리즘의 결정판이다.

판단 포인트: 희소 그래프는 Kruskal (간선 정렬 + Union-Find), 밀집 그래프는 Prim (우선순위 큐 기반)을 선택하는 것이 표준 기준이다.

Ⅰ. 개요 및 필요성

신장 트리 (Spanning Tree)란 그래프의 모든 정점을 포함하고 사이클이 없는 연결 부분 그래프다. MST는 신장 트리 중 간선 가중치 합이 최소인 것이다.

특성	내용
정점 수	V
간선 수	V-1 (트리 특성)
조건	연결 그래프, 무방향, 가중치
유일성	가중치가 모두 다르면 유일

MST가 필요한 상황:

네트워크 케이블 배선 최소 비용 계산
군집 분석 (Clustering): MST 간선 제거로 클러스터 분리
근사 TSP (1.5배 근사의 Christofides 알고리즘 기반)
전력 그리드, 통신망 설계

📢 섹션 요약 비유: MST는 여러 도시를 전화선으로 연결할 때 가장 적은 케이블로 모든 도시를 연결하는 방법이다.

Ⅱ. 아키텍처 및 핵심 원리

MST 핵심 속성 2가지

컷 속성 (Cut Property): 임의의 컷 (S, V-S)에서 양쪽을 잇는 최소 가중치 간선은 반드시 MST에 포함된다.

사이클 속성 (Cycle Property): 임의의 사이클에서 최대 가중치 간선은 MST에 포함되지 않는다.

Kruskal 알고리즘

1. 모든 간선을 가중치 기준 오름차순 정렬
2. 각 간선 (u, v)에 대해:
   - u와 v가 다른 컴포넌트면 간선 추가 + Union
   - 같은 컴포넌트면 사이클 형성 → 스킵
3. V-1개 간선 선택 완료 → MST 완성

Prim 알고리즘

1. 임의 정점에서 시작 → MST 집합에 추가
2. MST 집합과 인접한 간선 중 최솟값 선택
3. 선택된 정점이 MST에 없으면 추가
4. V-1번 반복 → MST 완성

ASCII 다이어그램 — MST 구성 과정

┌──────────────────────────────────────────────────────────┐
│  그래프:                                                  │
│    A ─(4)─ B ─(2)─ D                                     │
│    │       │       │                                     │
│   (1)     (3)     (5)                                     │
│    │       │       │                                     │
│    C ─(6)──────────┘                                     │
│                                                          │
│  Kruskal (간선 정렬):                                     │
│  [(1,AC),(2,BD),(3,BC),(4,AB),(5,CD),(6,CD)]              │
│                                                          │
│  Step1: (1) A-C 추가 ✓  [A-C]                            │
│  Step2: (2) B-D 추가 ✓  [A-C, B-D]                       │
│  Step3: (3) B-C 추가 ✓  [A-C, B-D, B-C] → A,B,C,D 연결  │
│  Step4: (4) A-B 사이클! → 스킵                            │
│  결과: MST 가중치 합 = 1+2+3 = 6                           │
│                                                          │
│  MST:  A ─(1)─ C ─(3)─ B ─(2)─ D                        │
└──────────────────────────────────────────────────────────┘

알고리즘 복잡도 비교

알고리즘	시간 복잡도	자료구조	적합 그래프
Kruskal	O(E log E)	Union-Find + 정렬	희소 (Sparse)
Prim (이진 힙)	O(E log V)	우선순위 큐	밀집 (Dense)
Prim (피보나치 힙)	O(E + V log V)	피보나치 힙	매우 밀집

📢 섹션 요약 비유: Kruskal은 전국 도로를 공사비 순서로 정렬해서 싼 것부터 연결하는 방식, Prim은 한 도시에서 시작해 가장 가까운 도시를 하나씩 흡수하는 방식이다.

Ⅲ. 비교 및 연결

Kruskal vs Prim 심층 비교

항목	Kruskal	Prim
출발점	없음 (전역 간선 정렬)	임의 시작 정점 필요
핵심 자료구조	Union-Find	우선순위 큐
병렬화	간선 정렬 병렬 가능	어려움
희소 그래프	유리 (간선 수 적음)	불리 (V² 탐색)
밀집 그래프	불리 (정렬 비용)	유리 (작은 큐)

MST 응용 — 근사 클러스터링

MST 완성 후 가중치 상위 k-1개 간선 제거
→ k개의 클러스터 자동 생성
→ O(E log E) 계층적 클러스터링 (Hierarchical Clustering)

📢 섹션 요약 비유: MST 클러스터링은 지도에서 가장 먼 도로부터 끊어내어 자연스러운 권역을 나누는 것과 같다.

Ⅳ. 실무 적용 및 기술사 판단

실무 시나리오

시나리오 1: 데이터센터 네트워크 케이블 설계

서버 노드 V=500, 가능한 연결 E=5,000
Kruskal: 5,000개 간선 정렬 + Union-Find = O(E log E) 빠른 처리
MST = 499개 간선으로 최소 비용 연결

시나리오 2: 이미지 세분화 (Image Segmentation)

픽셀을 정점, 유사도를 간선 가중치로 모델링
MST 기반 Graph Cut으로 물체 경계 검출

시나리오 3: 근사 TSP (외판원 문제 근사)

MST 구성 후 DFS로 해밀턴 경로 근사
이론적으로 최적해의 2배 이내 보장

기술사 판단 포인트

상황	선택
E ≪ V² (희소)	Kruskal
E ≈ V² (밀집)	Prim
간선 가중치 동점	MST 비유일 → 여러 MST 존재
동적 간선 추가	온라인 MST 알고리즘 (Borůvka 기반)
클러스터링	MST 상위 k-1 간선 제거

📢 섹션 요약 비유: 기술사 관점에서 MST 알고리즘 선택은 "데이터의 밀도"를 먼저 파악하는 것이다. 간선이 드문 그래프에서 Prim을 쓰면 우선순위 큐가 빈 채로 많은 시간을 낭비한다.

Ⅴ. 기대효과 및 결론

MST (Minimum Spanning Tree)는 "모든 노드를 최소 비용으로 연결"하는 탐욕적 해법으로, Kruskal과 Prim 두 알고리즘이 그래프 밀도에 따라 상호 보완적으로 사용된다. 네트워크 설계부터 클러스터링, 근사 TSP까지 광범위한 응용이 있다.

핵심 결론: MST = 컷 속성과 사이클 속성의 탐욕적 활용. "최솟값 간선을 추가해도 사이클이 생기지 않으면 반드시 MST에 포함"이라는 단순한 원리가 전체 알고리즘을 지탱한다.

📢 섹션 요약 비유: MST는 뼈대만 남긴 집 설계도 같다. 모든 방을 연결하되 불필요한 복도(간선)를 없애고, 가장 저렴한 재료(최소 가중치)로 구성한 최소한의 구조다.

📌 관련 개념 맵

개념	관계	설명
Kruskal 알고리즘	구현 방법	간선 정렬 + Union-Find
Prim 알고리즘	구현 방법	우선순위 큐 기반 확장
Union-Find	자료구조	Kruskal 사이클 검사
컷 속성 (Cut Property)	정확성 증명	최솟값 간선 포함 보장
근사 TSP	응용	MST 기반 2배 근사
클러스터링	응용	MST 간선 제거로 클러스터 분리

📈 관련 키워드 및 발전 흐름도

[가중 그래프 (Weighted Graph) — 간선에 비용이 존재하는 연결 구조]
    │
    ▼
[MST (Minimum Spanning Tree) — 모든 정점을 최소 비용으로 연결하는 트리]
    │
    ▼
[크루스칼 (Kruskal) vs 프림 (Prim) — 간선 정렬 vs 우선순위 큐 기반 접근]
    │
    ▼
[유니온-파인드 (Union-Find) — 크루스칼 사이클 판별을 위한 서로소 집합 구조]
    │
    ▼
[네트워크 설계 최적화 — 통신망·도로망·배관 설계의 최소 비용 연결 기반]

이 흐름은 가중 그래프에서 최소 비용 연결 구조인 MST의 개념이 확립되고, 크루스칼·프림 알고리즘을 통해 효율적으로 구현되며, 실제 네트워크 설계에 적용되는 과정을 보여준다.

👶 어린이를 위한 3줄 비유 설명

🏙️ MST는 5개 마을을 전화선으로 연결할 때, 가장 짧은 케이블만으로 모든 마을을 연결하는 방법이다.
✂️ Kruskal은 가장 짧은 케이블부터 연결하고, 이미 연결된 마을끼리 또 연결하는 낭비는 피한다.
🌱 Prim은 한 마을에서 시작해 가장 가까운 이웃 마을을 하나씩 흡수하며 네트워크를 키워나간다.