최소 신장 트리: 모든 걸, 싸게 연결

"집들의 마을이 있고 아무 쌍 사이든 케이블 까는 가격이 있어. 모든 집에 닿는 가장 싼 배선이 뭐야? 그게 최소 신장 트리야 — 그리고 가장 싼 안전한 엣지를 탐욕적으로 잡는 게 실제로 최적 답을 줘."

MST 가 뭔지 (그리고 아닌지)

가중 연결 그래프의 최소 신장 트리는 모든 정점을 연결하는 가장 싼 엣지 집합이야 — 정확히 V−1 엣지를 써 트리 (순환 없음) 를 이뤄. '이 네트워크 전체를 배선하는 최소-비용 방법이 뭐야?' 에 답해. 결정적으로, MST 는 두 특정 노드 사이 최단 경로에 관한 게 아니야; 모든 걸 연결 유지하는 총 엣지 무게를 최소화해. MST 에서 두 특정 집 사이 경로가 필요보다 길 수도 있어 — 괜찮아, 목표가 빠른 점대점 이동이 아니라 싼 전역 연결성이니까.

Kruskal 알고리즘: 가장 싼 엣지부터

Kruskal 은 아름답게 탐욕적이고 지난 lesson 의 도구를 재사용해: 모든 엣지를 무게로 정렬하고, 가장 싼 것부터 추가, 두 끝점이 이미 연결된 엣지는 건너뛰기 (그게 순환 만듦). '이미 연결됐어?' 가 정확히 find 질문이야 — 그래서 Union-Find 가 엔진: 다른 집합이면 끝점을 union, 루트 공유하면 엣지 건너뛰기. V−1 엣지 추가하면 멈춰. MST 전체가 '엣지 정렬 + union-find 순환 확인' 에서 떨어져. 정렬에 O(E log E).

Prim 알고리즘: 씨앗에서 키우기

Prim 은 다른 각도를 취해: 아무 정점 하나에서 시작해 트리를 바깥으로 키워, 지금까지 트리를 새 정점에 연결하는 가장 싼 엣지를 반복 추가. '새 정점으로 가장 싼 엣지' 가 최소-힙 쿼리야 — 그래서 Prim 은 MST 에 Dijkstra 가 최단 경로에 그렇듯, 둘 다 Heaps 트랙의 우선순위 큐로 굴러. Kruskal 은 엣지로 생각하고 (다 정렬); Prim 은 frontier 키우기로 생각해 (가로지르는 엣지의 힙). 둘 다 유효한 MST 를 만들어.

MST 는 최소 총 엣지 무게로 모든 정점 연결 (V−1 엣지, 순환 없음) — 가장 싼 전역 연결성이지 쌍별 최단 경로가 아니야. Kruskal = 엣지 정렬 + 순환 안 만드는 가장 싼 거 추가 (Union-Find); Prim = 최소-힙으로 씨앗에서 키우기. 여기선 탐욕이 증명 가능하게 최적.

왜 여기선 탐욕이 통하나 (보통 안 통해)

탐욕 알고리즘은 종종 틀려 — 국소적으로 최선인 선택 잡기가 전역 최적을 자주 놓쳐 (Paradigms 트랙에서 이게 실패하는 걸 봐). MST 는 탐욕이 증명 가능하게 정확한 유명한 경우 중 하나야, cut property 덕에: 정점을 두 그룹으로 나누는 어떤 방식에든, 그 분할을 가로지르는 단 하나의 가장 싼 엣지는 늘 어떤 MST 에 포함하기 안전해. Kruskal 이랑 Prim 둘 다 늘 가장 싼 가로지르는 엣지를 취하는 규율 있는 방법일 뿐이야. 네트워크 배선 너머, MST 는 클러스터링 (MST 짓고, 가장 비싼 k−1 엣지를 잘라 k 개 자연 클러스터) 이랑 외판원 문제 근사를 굴려.

피파의 고백

난 탐욕이 늘 가끔 지는 지름길이라 가정했어 — 가장-싼-거-잡기가 최적이기엔 너무 순진해 보였어. 그러다 아빠가 cut property 를 짚어줬고 봤어: MST 엔, 탐욕 선택이 보통이 아니라 보장된 안전이야. 탐욕을 재구성했어 — 본질적으로 엉성한 게 아니라, cut property 같은 속성이 받칠 때 정확히 맞는 전략이야. 탐욕이 언제 증명 가능하게 맞는지 아는 게 진짜 능력이고, MST 가 그게 값하는 가장 깔끔한 예야.

Code

Union-Find 순환 확인 있는 Kruskal MST·python

# Kruskal MST, 지난 lesson 의 Union-Find 위에.
class UnionFind:
    def __init__(self, elems):
        self.parent = {e: e for e in elems}
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path-halving
            x = self.parent[x]
        return x
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False        # 같은 집합 -> 엣지가 순환 만듦
        self.parent[ry] = rx
        return True

def kruskal(nodes, edges):
    """edges: (weight, u, v) 리스트. MST 엣지 리스트 + 총 비용 반환."""
    uf = UnionFind(nodes)
    mst, total = [], 0
    for w, u, v in sorted(edges):        # 가장 싼 엣지부터
        if uf.union(u, v):               # 별개 집합 둘을 연결할 때만 추가
            mst.append((u, v, w))
            total += w
    return mst, total

nodes = ["A", "B", "C", "D"]
edges = [(1,"A","B"), (3,"A","C"), (4,"B","C"), (2,"C","D"), (5,"B","D")]
mst, total = kruskal(nodes, edges)
print("MST edges:", mst)     # [('A','B',1), ('C','D',2), ('A','C',3)]
print("total cost:", total)  # 6 — 넷 다 연결하는 가장 싼 방법, 순환 없음
# 무게 4 의 B-C 엣지는 건너뜀: B 랑 C 가 A 통해 이미 연결됨.

Exercise

엣지 A-B(1), B-C(2), A-C(3), C-D(4) 에 Kruskal 을 손으로 돌려. 정렬하고, 가장 싼 것부터 추가, 순환 만드는 건 건너뛰기 — MST 엣지랑 총 비용을 나열하고, 건너뛰는 엣지랑 왜인지 대봐. 그다음 Union-Find 가 어떻게 Kruskal 한테 엣지가 순환을 만들 거라 알려주는지 한 문장으로 설명해.

Hint

정렬: A-B(1), B-C(2), A-C(3), C-D(4). A-B 추가, B-C 추가; A-C 는 A 랑 C 가 이미 연결 (같은 Union-Find 루트) 이라 건너뜀 — 추가하면 순환. C-D 추가. MST = {A-B, B-C, C-D}, 총 7. Union-Find 는 find(u) == find(v) 면 순환을 표시.

MST 가 뭔지 (그리고 아닌지)

Kruskal 알고리즘: 가장 싼 엣지부터

Prim 알고리즘: 씨앗에서 키우기

왜 여기선 탐욕이 통하나 (보통 안 통해)

피파의 고백

Code

External links

Exercise

Progress

댓글 0