한양과기고 에듀테크 수업도구 대시보드

최소 신장 트리 (Minimum Spanning Tree)

여러 도시를 도로로 모두 연결하되, 깔린 도로의 길이 합을 최소로 하려면? 이게 MST 문제다. 정점 V개를 사이클 없이 이으려면 정확히 V-1개의 간선이 필요하고, 그중 가중치 합이 가장 작은 연결 방법이 최소 신장 트리다. 두 대표 알고리즘 모두 탐욕적(greedy)으로 동작한다 — Kruskal은 가장 싼 간선부터 훑으며 사이클만 아니면 채택하고, Prim은 한 정점에서 나무를 키우며 매번 나무에 닿는 가장 싼 간선을 붙인다. 신기하게도 매 순간 "지금 제일 싼 것"만 골라도 전체 최적이 보장된다(절단 성질, cut property).

그래프에서 MST 만들기

속도

후보 간선 지금 검사 중 MST에 채택 사이클 → 버림 Prim 경계 간선 나무에 포함

실행 또는 한 단계를 눌러 MST가 만들어지는 과정을 지켜보세요.

MST 총 가중치

–

채택한 간선

0 / 8

검사한 간선

Kruskal — 간선 정렬 + 유니온-파인드

def kruskal(n, edges):        # edges = [(w, u, v), ...]
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # 경로 압축
            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                    # 간선 V-1개 모이면 완성

왜 유니온-파인드? "이 간선을 넣으면 사이클이 생기나?"는 곧 "두 끝점이 이미 같은 덩어리인가?"와 같다. find 두 번으로 O(α(n))에 판정.
정렬이 O(E log E)로 지배적 → 전체 O(E log E). 간선이 적은(희소) 그래프에 유리.
간선을 싼 것부터 보므로, 중간에 끊긴 숲(forest)들이 점점 합쳐지다 하나의 나무가 된다.

Prim — 한 점에서 나무 키우기 (우선순위 큐)

import heapq

def prim(n, adj, start=0):   # adj[u] = [(w, v), ...]
    in_tree = [False] * n
    pq = [(0, start, -1)]        # (간선 비용, 도착 정점, 출발 정점)
    mst, total = [], 0
    while pq and len(mst) < n - 1:
        w, v, u = heapq.heappop(pq)
        if in_tree[v]:
            continue                # 이미 나무 안 → 이 간선은 사이클
        in_tree[v] = True
        if u != -1:
            mst.append((u, v, w)); total += w
        for nw, nx in adj[v]:      # 새로 닿게 된 경계 간선들 추가
            if not in_tree[nx]:
                heapq.heappush(pq, (nw, nx, v))
    return mst, total

나무에 한 정점씩 붙는다. 매 단계에서 "나무 ↔ 바깥"을 잇는 간선 중 가장 싼 것을 우선순위 큐로 뽑는다.
인접 리스트 + 이진 힙이면 O(E log V), 피보나치 힙이면 O(E + V log V). 간선이 많은(조밀) 그래프에 유리.
다익스트라와 코드가 거의 같다 — 차이는 큐에 넣는 값이 "시작점부터의 누적 거리"가 아니라 "간선 하나의 비용"이라는 점뿐.

Kruskal vs Prim · 어디에 쓰나

구분	Kruskal	Prim
고르는 방식	전체에서 싼 간선 순서대로	나무에 닿는 싼 간선부터
중간 상태	여러 조각(숲)이 합쳐짐	항상 하나의 연결된 나무
핵심 자료구조	정렬 + 유니온-파인드	우선순위 큐(최소 힙)
시간복잡도	O(E log E)	O(E log V)
유리한 그래프	희소(간선 적음)	조밀(간선 많음)

통신·전력·상수도 망 설계: 모든 거점을 최소 케이블/배관으로 연결. MST의 원조 문제(1926년 전력망).
이미지 분할·군집화: 픽셀 그래프의 MST에서 비싼 간선을 끊으면 자연스러운 영역 경계가 된다.
근사 알고리즘: 외판원 문제(TSP)의 2배 근사해가 MST에서 나온다.
네트워크 브로드캐스트: 스패닝 트리 프로토콜(STP)이 스위치 루프를 없애려 신장 트리를 만든다.