Kruskal과 Prim은 어떻게 minimum spanning tree를 만드나요?

Question

Accepted Answer

**Minimum spanning tree(MST, 최소 신장 트리)**는 가중 연결 그래프의 모든 정점을 **최소 총 간선 가중치**로 사이클 없이 연결합니다. **Kruskal**과 **Prim**은 두 가지 전형적인 greedy 알고리즘입니다.

## Kruskal (간선 정렬, union-find)

모든 간선을 가중치로 정렬하고, 사이클을 만들지 않는 가장 싼 간선을 추가합니다.

```python
def kruskal(n, edges):                 # edges: (가중치, u, v)
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path compression
            x = parent[x]
        return x
    mst, total = [], 0
    for w, u, v in sorted(edges):      # 가장 싼 것부터
        ru, rv = find(u), find(v)
        if ru != rv:                   # 사이클 없음 -> 채택
            parent[ru] = rv
            mst.append((u, v, w)); total += w
    return mst, total
```

## Prim (min-heap으로 트리를 키움)

임의의 정점에서 시작하여, 현재 트리를 떠나는 가장 싼 간선을 반복적으로 추가합니다.

## 비교

| | Kruskal | Prim |
|---|--------|------|
| 접근 | 간선 정렬 + union-find | 노드에서 키움 + heap |
| 시간 | O(E log E) | O(E log V) |
| 적합한 경우 | 희소 그래프 | 밀집 그래프 |

## 언제 사용하나 / 함정

**네트워크 설계** — 케이블 부설, 수도관, 클러스터링 — 에 MST를 사용하세요. 둘 다 greedy이며 여기서 증명 가능하게 최적입니다. Kruskal은 사이클을 효율적으로 피하기 위해 union-find가 필요합니다.

## 왜 중요한가

MST는 모든 것을 연결하는 비용을 최소화합니다 — 인프라와 네트워크 레이아웃에 직접 적용됩니다.

greedy가 증명 가능하게 최적인 깔끔한 사례로, 탐욕 선택 추론을 강화합니다.

Kruskal은 또한 폭넓은 알고리즘적 활용도를 지닌 구조인 union-find를 보여 줍니다.

	Kruskal	Prim
접근	간선 정렬 + union-find	노드에서 키움 + heap
시간	O(E log E)	O(E log V)
적합한 경우	희소 그래프	밀집 그래프