최소 신장 트리 ( MST : Minimal Spanning Tree )

최소 신장 트리(Minimum Spanning Tree, MST)는 그래프에서 모든 노드를 연결하는 트리 중 가중치의 합이 최소가 되는 트리를 의미합니다. 그래프의 모든 정점을 연결하되 사이클이 없고, 간선들의 가중치 합이 가장 작은 트리 구조를 찾는 것이 목적입니다. 이 문제는 컴퓨터 네트워크, 배전망 설계, 경로 최적화 등 다양한 분야에서 유용하게 사용됩니다.

최소 신장 트리를 구하는 대표적인 알고리즘에는 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 있습니다. 두 알고리즘 모두 서로 다른 방식으로 최소 신장 트리를 구하는 문제를 해결합니다.

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

크루스칼 알고리즘은 간선 중심의 알고리즘으로, 그래프의 간선들을 가중치 순으로 정렬한 다음 가장 낮은 가중치의 간선을 선택하며 트리를 만들어 나가는 방식입니다.

• 과정:
  1. 그래프의 모든 간선을 가중치 오름차순으로 정렬합니다.
  2. 사이클을 형성하지 않는 간선을 선택하고, 이를 신장 트리에 추가합니다.
  3. 모든 정점이 연결될 때까지 위의 과정을 반복합니다.
• 장점: 모든 간선을 한번에 정렬하고 시작하므로 간선의 수가 적을 때 적합합니다.
• 시간 복잡도: 간선의 개수가 E, 정점의 개수가 V일 때, O(Elog⁡E)로 간선 정렬에 지배됩니다.

예시:

1. 간선을 가중치 기준으로 정렬합니다.
2. 최소 가중치의 간선부터 차례대로 추가하여 트리를 만듭니다. 사이클이 발생하지 않도록 주의합니다.

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

프림 알고리즘은 정점 중심의 알고리즘으로, 임의의 정점에서 시작하여 트리의 정점과 연결된 간선 중 가중치가 가장 작은 간선을 선택하며 트리를 확장해 나갑니다.

• 과정:
  1. 임의의 시작 정점을 선택합니다.
  2. 선택된 정점과 연결된 간선 중 가중치가 가장 작은 간선을 선택하여 신장 트리에 추가합니다.
  3. 새로운 정점을 선택하여 이 과정을 반복합니다. 모든 정점이 포함될 때까지 계속합니다.
• 장점: 특정 정점에서 출발하여 탐색하므로 간선의 수가 많을 때 적합합니다.
• 시간 복잡도: 인접 리스트를 사용하고 우선순위 큐를 활용하면 O(E log ⁡V)의 시간 복잡도를 가집니다.

예시:

1. 시작 정점을 선택하고, 그 정점에 연결된 간선 중 최소 가중치를 가진 간선을 선택합니다.
2. 새로 추가된 정점에서 다른 연결된 간선을 선택하며 트리를 확장합니다.

예제

다음은 그래프가 주어졌을 때 크루스칼 알고리즘과 프림 알고리즘을 사용하여 최소 신장 트리를 찾는 예제입니다.

예제 그래프

• 정점: A, B, C, D
• 간선 및 가중치:
  
  • A-B: 1
  • A-C: 3
  • B-C: 3
  • B-D: 4
  • C-D: 2

크루스칼 알고리즘으로 MST 찾기

1. 간선을 가중치 기준으로 정렬: A-B(1), C-D(2), A-C(3), B-C(3), B-D(4).
2. A-B를 선택 (가중치 1).
3. C-D를 선택 (가중치 2).
4. A-C를 선택 (가중치 3).
   • 이제 모든 정점(A, B, C, D)이 연결되었으므로 끝.

최소 신장 트리는 A-B, C-D, A-C로 구성되고 가중치 합은 1+2+3=6입니다.

프림 알고리즘으로 MST 찾기

1. 임의의 정점 A에서 시작합니다.
2. A와 연결된 간선 중 가중치가 가장 작은 A-B(1)을 선택합니다.
3. B와 연결된 간선 중 가중치가 가장 작은 C-D(2)를 선택합니다.
4. C와 연결된 간선 중 가중치가 가장 작은 A-C(3)를 선택합니다.

최소 신장 트리는 A-B, C-D, A-C로 구성되고 가중치 합은 1+2+3=6입니다.

최소 신장 트리의 활용

• 네트워크 설계: 통신망, 전력망, 도로망 등을 최소 비용으로 설계하는 데 사용됩니다.
• 클러스터링: 데이터 간의 유사성을 기반으로 군집을 형성하는 클러스터링에도 사용됩니다.
• 경로 최적화: 자원의 이동 경로를 최적화하거나 비용을 줄이는 문제를 해결할 수 있습니다.

Python 예제 코드 (프림 알고리즘)

다음은 Python을 이용하여 프림 알고리즘을 구현한 간단한 예제 코드입니다.

import heapq
from collections import defaultdict

def prim(graph, start):
    mst = []
    visited = set([start])
    edges = [
        (cost, start, to) for to, cost in graph[start].items()
    ]
    heapq.heapify(edges)

    while edges:
        cost, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst.append((frm, to, cost))

            for next_to, next_cost in graph[to].items():
                if next_to not in visited:
                    heapq.heappush(edges, (next_cost, to, next_to))

    return mst

graph = {
    'A': {'B': 1, 'C': 3},
    'B': {'A': 1, 'C': 3, 'D': 4},
    'C': {'A': 3, 'B': 3, 'D': 2},
    'D': {'B': 4, 'C': 2}
}

mst = prim(graph, 'A')
print("Minimum Spanning Tree:", mst)

이 코드는 프림 알고리즘을 사용하여 주어진 그래프의 최소 신장 트리를 계산합니다.

결론

최소 신장 트리는 네트워크 설계나 경로 최적화 같은 다양한 문제를 해결하는 데 매우 유용한 개념입니다. 크루스칼 알고리즘과 프림 알고리즘은 서로 다른 방식으로 최소 신장 트리를 찾으며, 문제의 조건에 따라 적절한 알고리즘을 선택하는 것이 중요합니다.