IT용어위키

최소 신장 트리(Minimum Spanning Tree, MST)는 그래프에서 모든 정점을 연결하는 간선들의 부분 그래프 중에서, 간선 가중치의 합이 최소가 되는 신장 트리를 의미한다. MST는 네트워크 설계, 클러스터링, 영상 처리 등 다양한 분야에서 활용된다.

정의

신장 트리(Spanning Tree)는 주어진 그래프의 모든 정점을 포함하면서, 사이클이 없는 부분 그래프이다.

최소 신장 트리(MST)는 가능한 모든 신장 트리 중에서 간선의 가중치 합이 최소인 트리이다.

최소 신장 트리의 성질

V개의 정점을 포함하는 MST는 V-1개의 간선을 가진다.
사이클이 존재하지 않는다.
연결 그래프에서만 존재할 수 있으며, 비연결 그래프에서는 MST를 찾을 수 없다.
MST는 유일하지 않을 수 있다. 여러 개의 최소 신장 트리가 존재할 수 있다.

최소 신장 트리 알고리즘

MST를 찾는 대표적인 알고리즘은 다음과 같다.

크루스칼 알고리즘 (Kruskal's Algorithm)

크루스칼 알고리즘은 간선을 오름차순으로 정렬한 후, 사이클을 형성하지 않는 간선을 하나씩 선택하여 MST를 구성하는 방식이다.

알고리즘 과정:

그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다.
사이클을 만들지 않는 간선을 선택하여 MST에 추가한다.
V-1개의 간선이 선택될 때까지 반복한다.

슈도코드:

KruskalMST(graph):
    result = []
    edges = graph.edges sorted by weight
    disjointSet = new DisjointSet(graph.vertices)

    for each edge (u, v, weight) in edges:
        if disjointSet.find(u) != disjointSet.find(v):
            result.append((u, v, weight))
            disjointSet.union(u, v)

    return result

파이썬 코드:

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
    
    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        rootU = self.find(u)
        rootV = self.find(v)
        if rootU != rootV:
            self.parent[rootU] = rootV

def kruskal_mst(graph):
    edges = sorted(graph, key=lambda x: x[2])  # 간선 정렬 (u, v, weight)
    ds = DisjointSet(len(graph))
    mst = []

    for u, v, weight in edges:
        if ds.find(u) != ds.find(v):
            ds.union(u, v)
            mst.append((u, v, weight))
    
    return mst

프림 알고리즘 (Prim's Algorithm)

프림 알고리즘은 시작 정점에서 출발하여, MST에 포함되지 않은 정점 중 최소 가중치의 간선을 추가하는 방식이다.

알고리즘 과정:

임의의 정점에서 시작하여 MST에 추가한다.
MST에 연결된 간선 중 최소 가중치를 가지는 간선을 선택한다.
선택된 간선을 MST에 추가한 후, 해당 간선의 도착 정점을 MST에 포함시킨다.
모든 정점이 포함될 때까지 반복한다.

슈도코드:

PrimMST(graph, start):
    MST = []
    minHeap = PriorityQueue()
    visited = set()

    minHeap.push((0, start))  # 시작 정점

    while minHeap is not empty:
        weight, u = minHeap.pop()
        if u in visited:
            continue
        visited.add(u)
        MST.append(u)

        for v, w in graph[u]:
            if v not in visited:
                minHeap.push((w, v))

    return MST

파이썬 코드:

import heapq

def prim_mst(graph, start=0):
    mst = []
    visited = set()
    min_heap = [(0, start)]  # (가중치, 정점)
    
    while min_heap:
        weight, u = heapq.heappop(min_heap)
        if u in visited:
            continue
        visited.add(u)
        mst.append(u)

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

    return mst

최소 신장 트리의 응용

네트워크 설계
- 전력망, 통신 네트워크, 도로망 최적화.

클러스터링
- 데이터 군집화(K-means, 계층적 클러스터링).

영상 처리
- 이미지 분할 및 객체 탐지.

항공 경로 최적화
- 최소 비용으로 도시 간 비행 경로 설정.

같이 보기

참고 문헌

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.
Wikipedia - Minimum Spanning Tree