최소 신장 트리: 전부를 싸게 잇기

"집들이 모인 마을이 있고 아무 두 집 사이에나 케이블을 까는 가격이 정해져 있어. 모든 집에 닿는 가장 싼 배선은 뭘까? 그게 최소 신장 트리야. 그리고 가장 싸면서 안전한 간선을 탐욕적으로 집어 가면 실제로 최적의 답이 나와."

MST가 뭐고 뭐가 아닌지

가중치가 붙은 무방향 연결 그래프의 최소 신장 트리는 모든 정점을 잇는 간선 집합 중 가중치 총합이 가장 작은 거야. 간선을 정확히 V−1개 쓰지. 그래프가 연결돼 있지 않다면 MST 하나가 아니라 연결 요소마다 최소 신장 포리스트를 얻게 되고. MST는 특정한 두 노드 사이의 최단 경로가 아니라 전체 연결 비용을 최소화하는 문제라는 걸 계속 붙들고 가.

Kruskal 알고리즘: 가장 싼 간선부터

Kruskal은 아름다울 만큼 탐욕적이고, 바로 앞에서 만든 도구를 그대로 재사용해. 모든 간선을 가중치 순으로 정렬하고, 싼 것부터 넣되, 양 끝점이 이미 이어져 있는 간선은 건너뛰는 거야. 그런 간선을 넣으면 순환이 생기니까. 그리고 '이미 이어져 있나?'가 정확히 find가 답하는 질문이지. 그래서 Union-Find가 엔진이 돼. 두 끝점이 다른 집합이면 union하고, 루트가 같으면 그 간선은 건너뛰어. 간선을 V−1개 넣으면 멈추고. MST 전체가 '간선 정렬 + union-find 순환 검사'에서 툭 떨어지는 거야. 전체 비용은 정렬이 지배해서 O(E log E)고.

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

Prim은 반대 각도에서 접근해. 아무 정점 하나에서 시작해 트리를 바깥으로 키워 나가는데, 지금까지 만든 트리를 아직 안 들어온 정점에 잇는 가장 싼 간선을 반복해서 추가해. '새 정점으로 가는 가장 싼 간선'이 곧 최소 힙 질의라서, 최단 경로에 Dijkstra가 있듯 MST에는 Prim이 있는 셈이야. 둘 다 힙 트랙의 우선순위 큐 위에서 돌아가고. Kruskal은 간선 단위로 생각하고(전부 정렬해서), Prim은 자라나는 경계로 생각해(가로지르는 간선을 담은 힙으로). 어느 쪽이든 유효한 MST가 나와.

MST는 가중치 총합을 최소로 하면서 모든 정점을 잇는 거야. 간선이 V−1개고 순환은 없지. 전체 연결을 가장 싸게 하는 문제지 두 노드 사이 최단 경로가 아니고. Kruskal은 간선을 정렬해서 순환을 안 만드는 가장 싼 것부터 넣는 방식이고 Union-Find를 써. Prim은 최소 힙으로 한 점에서 키워 나가는 방식이고. 여기서는 탐욕이 증명 가능하게 최적이야.

왜 여기서는 탐욕이 통할까

MST에서 탐욕이 맞는 근거는 cut property야. 어떤 cut을 가로지르는 간선 중 가중치가 가장 작은 것은 적어도 하나의 MST에 넣어도 안전하다는 거지. 다만 최솟값이 여러 개로 동점이라면 그중 특정 간선 하나가 모든 MST에 반드시 들어간다는 뜻은 아니야. 그리고 MST를 이용한 TSP 근사는 완전 그래프의 거리 함수가 삼각부등식을 만족하는 metric TSP 같은 추가 전제가 있어야만 보장이 성립해.

피파의 고백

나는 탐욕이란 게 늘 가끔은 지는 지름길이라고 생각했어. 제일 싼 걸 집는 방식이 최적이기엔 너무 순진해 보였거든. 그러다 아빠가 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