최소 신장 트리(MST, Minimum Spanning Tree)

최소 신장 트리(MST, Minimum Spannig Tree)

최소 신장 트리란 가중치가 있는 무방향 그래프에서 모든 정점을 연결하면서도 간선의 가중치 합이 최소가 되는 트리입니다. 

위에 그림처럼 여러 신장 트리(모든 정점을 연결하는 트리)가 존재할 수 있으나, 간선의 가중치의 합이 가장 작은 트리가 최소 신장 트리입니다. 

---

최소 신장 트리의 필요성과 활용

• 네트워크 설계: 컴퓨터, 통신 기기를 최소 비용으로 연결
• 도로망 구축: 도시 간의 도로를 최적 비용으로 설계
• 클러스터링 및 데이터 분석: 데이터 포인트들 사이의 관계를 기반으로 군집 형성

MST는 최적의 비용으로 모든 요소를 연결해야 할 때 유용한 개념입니다. 

---

MST 알고리즘 

MST를 구하는 대표적인 알고리즘은 크루스칼(kruskal)과 프림(Prim) 알고리즘입니다. 

각 알고리즘의 기본 원리 및 구현 방법을 알아봅시다.

 

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

동작 원리

1. 간선 정렬: 모든 간선을 가중치 순으로 오름차순으로 정렬합니다. 
2. 사이클 판별: 정렬된 간선들을 순서대로 선택하는데, 이때 선택한 간선의 두 정점이 이미 같은 집합(연결 요소)에 속해 있다면 해당 간선을 건너뜁니다. → 이때 유니온 파인드(Union-Find) 자료구조를 사용해 효율적으로 판별합니다. 
3. 집합 병합: 두 정점이 서로 다른 집합에 속해 있다면 간선을 선택하고, 두 집합을 하나로 합칩니다. 
4. 종료 조건: 정점의 개수가 V인 그래프라면 V - 1개의 간선을 선택하면 MST가 완성됩니다.

크루스칼 파이썬 구현

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(a, b):
    root_a = find(a)
    root_b = find(b)
    if root_a != root_b:
        parent[root_b] = root_a  # 간단한 union: 작은 루트가 부모가 됨

# 간선 리스트 예시: (cost, a, b)
edges = [
    (1, 1, 2),
    (3, 1, 3),
    (2, 2, 3),
    (4, 2, 4),
    # 추가 간선들...
]

edges.sort()  # 가중치 오름차순 정렬

mst_cost = 0
for cost, a, b in edges:
    if find(a) != find(b):
        union(a, b)
        mst_cost += cost

print("최소 신장 트리의 비용:", mst_cost)

 

2. 프림 알고리즘

동작 원리

1. 시작 정점 선택: 임의의 정점에서 시작해, MST에 포함된 정점 집합을 초기화합니다. 
2. 최소 간선 선택: MST에 포함된 정점과 포함되지 않은 정점을 연결하는 간선 중 가중치가 가장 낮은 간선을 선택합니다.
3. 우선순위 큐 활용: 인접 간선을 효율적으로 선택하기 위해 우선순위 큐를 사용합니다. 
4. 정점 추가: 선택한 간선을 통해 새로운 정점을 MST에 추가하고, 이과정을 모든 정점이 포함될 때까지 반복합니다. 

프림 파이썬 구현

import heapq

# 그래프: 인접 리스트 (정점: [(가중치, 인접 정점), ...])
graph = {
    1: [(1, 2), (3, 3)],
    2: [(1, 1), (2, 3), (4, 4)],
    3: [(3, 1), (2, 2), (5, 4)],
    4: [(4, 2), (5, 3)]
}

visited = [False] * (n + 1)
min_cost = 0
pq = []

# 시작 정점 1에서 시작
visited[1] = True
for cost, next_vertex in graph[1]:
    heapq.heappush(pq, (cost, next_vertex))

while pq:
    cost, vertex = heapq.heappop(pq)
    if not visited[vertex]:
        visited[vertex] = True
        min_cost += cost
        for next_cost, next_vertex in graph[vertex]:
            if not visited[next_vertex]:
                heapq.heappush(pq, (next_cost, next_vertex))

print("최소 신장 트리의 비용:", min_cost)

---

MST 알고리즘의 장단점 비교

크루스칼 알고리즘

• 장점
  • 간선 중심의 접근으로 희소 그래프에 유리함
  • 유니온 파인드를 활용해 사이클 판별에 효율적임
• 단점
  • 모든 간선을 정렬해야 하므로, 간선의 수가 많은 경우 정렬 비용이 부담될 수 있음
  • 유니온 파인드 구현 시 최적화(경로 압축, union by rank) 필요

프림 알고리즘

• 장점
  • 한 정점에서부터 점진적으로 확장하므로 밀집 그래프에 효과적
  • 우선순위 큐를 활용하여 인접 간선 중 최소 비용 간선을 빠르게 선택
• 단점
  • 우선순위 큐의 구현 및 관리를 신경 써야 함
  • 정점과 인접 간선 정보를 관리하는 추가 오버헤드 발생