최소 신장 트리(MST) (Kruskal vs Prim 알고리즘 비교)

MST란? – 최소한의 비용으로 그래프를 ‘연결’하는 법

최소 신장 트리 (Minimum Spanning Tree)란,
모든 정점을 연결하면서, 전체 간선 가중치의 합이 최소가 되도록 구성된 트리

즉,

• 모든 노드를 연결하되
• 사이클 없이
• 전체 비용이 최소가 되도록

여기서 "트리(Tree)"는 사이클이 없는 연결 그래프를 의미합니다.

---

언제 필요한가? (실전 예시)

실전	상황설명
전기 배선 설계	건물 간 최소 전선 비용으로 연결
네트워크 케이블 배치	컴퓨터/라우터를 최소 거리로 연결
도로, 철도 노선 설계	최소 토목 비용으로 모든 지역 연결
데이터 클러스터링	거리 기반 클러스터 연결 구조 도출

---

MST 문제의 조건 정리

• 그래프는 연결 그래프여야 함
• 모든 간선의 가중치는 0 이상
• 여러 개의 MST가 존재할 수 있음 (중복 간선 비용)
• 핵심: 사이클이 생기지 않게 연결, 그리고 전체 비용 최소화

---

4. MST를 구하는 두 대표 알고리즘

알고리즘	특징
Kruskal	간선 중심: 비용이 낮은 간선부터 연결 (Union-Find 사용)
Prim	노드 중심: 현재 연결된 노드에서 가장 가까운 노드를 확장 (우선순위 큐 사용)

두 알고리즘의 전략은 완전히 다릅니다.
→ 아래에서 구조부터 차근차근 비교합니다.

---

Kruskal 알고리즘 – 간선을 정렬하라

핵심 로직

1. 간선을 비용 기준으로 정렬
2. 비용이 가장 낮은 간선을 하나씩 선택
3. 사이클이 생기지 않는다면 연결 → Union-Find로 확인

Python 구현

def kruskal(n, edges):
    parent = [i for i in range(n + 1)]

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        root_x, root_y = find(x), find(y)
        if root_x == root_y:
            return False
        parent[root_y] = root_x
        return True

    edges.sort(key=lambda x: x[2])
    total_cost = 0
    for u, v, cost in edges:
        if union(u, v):
            total_cost += cost

    return total_cost

---

Prim 알고리즘 – 인접한 가장 가까운 노드로 확장

핵심 로직

1. 아무 노드에서 시작
2. 인접 노드 중 가장 비용이 적은 간선 선택
3. 방문하지 않은 노드를 확장
4. 우선순위 큐(heap) 사용하여 최소 비용 선택

Python 구현

import heapq

def prim(n, graph):
    visited = [False] * (n + 1)
    heap = [(0, 1)]  # (cost, node)
    total_cost = 0

    while heap:
        cost, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        total_cost += cost
        for v, w in graph[u]:
            if not visited[v]:
                heapq.heappush(heap, (w, v))

    return total_cost

입력 형태 예시 (인접 리스트):

graph = {
    1: [(2, 3), (3, 1)],
    2: [(1, 3), (3, 7)],
    3: [(1, 1), (2, 7)]
}

---

Kruskal vs Prim 비교

항목	Kruskal	Prim
접근 방식	간선 중심	노드 중심
자료구조	Union-Find	Min-Heap (우선순위 큐)
그래프 형태	간선 리스트 유리	인접 리스트 유리
시간복잡도	O(E log E)	O(E log V)
구현 난이도	간단한 정렬 + 유니온파인드	힙 사용 필요 (복잡도 ↑)
실전 팁	간선 수가 적을 때 유리	밀집 그래프에서 유리

 

---

요약

항목	설명
MST 목적	모든 노드를 연결하며, 전체 비용 최소화
Kruskal	정렬 기반, Union-Find 사용, 간선 중심
Prim	힙 기반, 인접 리스트, 노드 중심
시간복잡도	O(E log E), O(E log V)
실전 선택 기준	그래프 밀도, 자료구조 형태에 따라 선택