[algorithm] 최소 스패닝 트리 (MST)

최소 스패닝 트리 (MST)란?

최소 스패닝 트리(MST, Minimum Spanning Tree)는 그래프 이론에서 중요한 개념 중 하나로, 주어진 그래프에서 모든 정점을 연결하는 트리 중에서 가중치의 합이 최소인 트리를 의미한다.

간단히 말해, 각 정점들이 연결되어 있으며, 연결된 모든 간선들의 가중치 합이 최소가 되는 트리를 찾는 문제

---

✅ 최소 스패닝 트리의 특징

1. 트리 구조:
   • MST는 반드시 트리 형태 (트리 : 사이클이 없는 연결된 그래프)
   • 트리의 특성상, N개의 정점이 있을 경우, 간선의 수는 항상 N-1
2. 최소 가중치:
   • MST는 모든 간선의 가중치 합이 최소가 되어야 한다. (ex. 가중치가 의미하는 것 : 도로의 비용, 네트워크 연결의 비용 등)
3. 그래프 연결:
   • MST는 그래프에 있는 모든 정점들을 연결해야 하므로, 주어진 그래프가 연결되어 있어야만 MST를 찾을 수 있다.
   • 만약 그래프가 연결되어 있지 않다면, MST는 존재하지 않음
4. 대표 알고리즘
   1. 크루스칼(Kruskal)
   2. 프림(Prim)

---

✅ 크루스칼(Kruskal) 알고리즘

크루스칼 알고리즘은 간선 중심의 알고리즘으로, 모든 간선을 가중치 순으로 정렬한 후, Union-Find 자료구조를 사용하여 사이클을 만들지 않도록 간선을 하나씩 선택해가며 트리를 확장해 나가는 방식

2025.02.05 - [algorithm/UnionFind] - [algorithm] 유니온-파인드(Union-Find) 알고리즘

[algorithm] 유니온-파인드(Union-Find) 알고리즘

 

 

알고리즘 절차:

1. 그래프의 모든 간선을 가중치 순으로 오름차순 정렬
2. 간선을 하나씩 선택하며, 사이클이 생기지 않으면 MST에 추가
3. 간선 수가 N-1개가 될 때까지 반복

예시 코드

# find 연산: 경로 압축 포함
def find(parent, u):
    if parent[u] != u:
        parent[u] = find(parent, parent[u])
    return parent[u]

# union 연산: 랭크 기반 병합
def union(parent, rank, u, v):
    root_u = find(parent, u)
    root_v = find(parent, v)

    if root_u != root_v:
        if rank[root_u] > rank[root_v]:
            parent[root_v] = root_u
        elif rank[root_u] < rank[root_v]:
            parent[root_u] = root_v
        else:
            parent[root_v] = root_u
            rank[root_u] += 1
        return True
    return False

# 크루스칼 알고리즘
def kruskal(n, edges):
    parent = [i for i in range(n)]
    rank = [0] * n
    mst = []

    edges.sort(key=lambda x: x[2])  # 가중치 기준 정렬

    for u, v, weight in edges:
        if union(parent, rank, u, v):  # 사이클 없으면 추가
            mst.append((u, v, weight))

    return mst

// 예시

edges = [
    (0, 1, 10),
    (0, 2, 6),
    (0, 3, 5),
    (1, 3, 15),
    (2, 3, 4)
]
n = 4
mst = kruskal(n, edges)
print("Kruskal MST:", mst)
# 출력: [(2, 3, 4), (0, 3, 5), (0, 1, 10)]

 

크루스칼 알고리즘의 주요 특징은 간선 중심으로 진행되며, Union-Find(집합 찾기) 자료구조를 사용해 사이클 여부를 판단한다.

---

✅ 프림(Prim) 알고리즘

프림 알고리즘은 정점 중심의 알고리즘으로, 시작 정점에서부터 차례대로 트리를 확장해 나가는 방식이다.

우선순위 큐를 사용하여 가장 비용이 적은 간선을 빠르게 선택

 

알고리즘 절차:

1. 임의의 정점에서 시작
2. 방문하지 않은 정점 중, 현재 트리와 연결되는 간선 중 최소 가중치 선택
3. 정점 수만큼 반복

예시 코드

import heapq

# 프림 알고리즘 구현
def prim(n, adj):
    mst = []
    visited = [False] * n
    min_heap = [(0, 0, -1)]  # (가중치, 현재 정점, 이전 정점)
    total_cost = 0

    while min_heap:
        weight, u, prev = heapq.heappop(min_heap)
        if visited[u]:
            continue
        visited[u] = True
        total_cost += weight
        if prev != -1:
            mst.append((prev, u, weight))

        for v, w in adj[u]:
            if not visited[v]:
                heapq.heappush(min_heap, (w, v, u))

    return mst, total_cost

// 예시
adj = [
    [(1, 10), (2, 6), (3, 5)],
    [(0, 10), (3, 15)],
    [(0, 6), (3, 4)],
    [(0, 5), (1, 15), (2, 4)]
]
n = 4
mst, total_cost = prim(n, adj)
print("Prim MST:", mst)
print("총 비용:", total_cost)
# 출력:
# Prim MST: [(0, 3, 5), (3, 2, 4), (0, 1, 10)]
# 총 비용: 19

 

 

프림 알고리즘은 우선순위 큐(priority queue)를 활용하여, 트리에서 연결할 간선들을 효율적으로 관리한다.

---

✅ 크루스칼과 프림 알고리즘 비교

항목	Kruskal	Prim
방식	간선 중심	정점 중심
정렬 필요 여부	간선 가중치 정렬 필요	불필요 (우선순위 큐 사용)
자료구조	Union-Find	우선순위 큐 (heap)
시간 복잡도	O(E log E)	O(E log V) (인접 리스트 + heap 기준)
적합한 그래프	간선이 적은 희소 그래프	정점이 많은 조밀 그래프

---

✅ 최소 스패닝 트리의 활용 예시

1. 네트워크 설계

컴퓨터 네트워크를 설계할 때, 여러 컴퓨터를 최소한의 비용으로 연결하려면 MST를 사용 가능

이때 비용은 네트워크 연결의 비용이나 거리로 측정

2. 전력망 설계

전력망을 설계할 때, 각 변전소를 최소한의 비용으로 연결하는 문제도 MST로 해결 가능

이 경우 각 변전소 간의 연결 비용을 가중치로 설정하여 최적화

3. 도로망 구축

도시나 국가의 도로망을 구축할 때, 각 도시를 최소 비용으로 연결하는 도로를 설계하는 데 MST를 사용 가능