최소 신장 트리

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

정의

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

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

최소 신장 트리의 성질

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

최소 신장 트리 알고리즘

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

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

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

알고리즘 과정:

1. 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다.
2. 사이클을 만들지 않는 간선을 선택하여 MST에 추가한다.
3. 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에 포함되지 않은 정점 중 최소 가중치의 간선을 추가하는 방식이다.

알고리즘 과정:

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

슈도코드:

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