Spanning Tree

스패닝 트리(Spanning Tree)

스패닝 트리(Spanning Tree) 는 무방향 그래프(Undirected Graph)의 모든 정점을 포함하면서, 사이클 없이 연결된 부분 그래프이다. 다시 말해, 원래 그래프의 모든 정점을 최소한의 간선으로 연결한 트리 구조이다.

신장 트리는 그래프 이론의 핵심 개념으로, 다양한 실제 문제 해결에 활용된다.
최소 신장 트리 알고리즘인 크루스칼, 프림, 보로프카는 각각 다른 상황에서 최적의 성능을 보이며, 알고리즘 선택은 그래프의 특성과 문제 요구사항에 따라 달라진다.

신장 트리의 응용은 네트워크 설계, 클러스터링, 이미지 처리 등 다양한 분야에 걸쳐 있으며, 그 변형과 확장은 더 복잡한 문제를 해결하는 데 도움이 된다. 최적화 기법과 효율적인 자료구조를 활용하면 대규모 그래프에서도 신장 트리를 효과적으로 계산할 수 있다.

스패닝 트리의 특징

• 주어진 그래프의 모든 정점을 포함
• N개의 정점(Vertex)이 있다면, 스패닝 트리는 항상 N-1개의 간선(Edge)을 가짐
• 사이클(Cycle)이 존재하지 않음
• 원본 그래프에서 일부 간선을 제거하여 트리를 생성

스패닝 트리의 예시

1
2
3
4

  A — B
  |  /|
  | / |
  C — D

정점(Vertex) = {A, B, C, D}
간선(Edge) = {(A-B), (B-D), (C-D), (A-C), (B-C)}

가능한 스패닝 트리

하나의 그래프에서 여러 개의 스패닝 트리가 존재할 수 있음.

1. 스패닝 트리 1

   1 2 3

   A — B | | C — D

   간선: {(A-B), (B-D), (C-D)}

2. 스패닝 트리 2

   1 2 3

   A — B | C — D

   간선: {(A-B), (A-C), (C-D)}

3. 스패닝 트리 3

   1 2 3

   A B \ / C — D

   간선: {(A-C), (B-C), (C-D)}

최소 스패닝 트리(Minimum Spanning Tree, MST)

• 모든 정점을 포함하면서, 간선 가중치(Weight)의 합이 최소가 되는 스패닝 트리
• 가중치 그래프(Weighted Graph)에서 최소 비용으로 모든 정점을 연결하는 트리
• 네트워크 설계, 전력망 구축, 도로 시스템 등에 활용

MST 예시

1
2
3
4
5

  A --(4)-- B
  |       |
 (2)     (3)
  |       |
  C --(1)-- D

최소 스패닝 트리 (MST)

1
2
3
4
5

  A --(2)-- C
            |
          (1)
            |
            D --(3)-- B

간선 가중치 합 = 2 + 1 + 3 = 6 (최소 비용)

스패닝 트리의 속성

신장 트리의 종류

1. 일반 신장 트리(Spanning Tree)
   그래프의 모든 정점을 포함하고 사이클이 없는 부분 그래프.

2. 최소 신장 트리(Minimum Spanning Tree, MST)
   가중치 그래프에서 간선의 가중치 합이 최소가 되는 신장 트리.
   네트워크 설계에서 비용을 최소화하는 데 활용된다.

3. 최대 신장 트리(Maximum Spanning Tree)
   가중치 그래프에서 간선의 가중치 합이 최대가 되는 신장 트리.
   특정 알고리즘 문제 해결에 사용된다.

4. 이차 최소 신장 트리(Second Best Minimum Spanning Tree)
   최소 신장 트리 다음으로 가중치 합이 작은 신장 트리이다. 네트워크 설계에서 대체 경로 계획에 활용된다.

5. 근사 최소 신장 트리(Approximate Minimum Spanning Tree)
   대규모 그래프에서 완전한 최소 신장 트리를 구하기 어려울 때 사용하는 근사 알고리즘으로 얻는 트리이다.

스패닝 트리 알고리즘

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

   • 그리디 알고리즘(Greedy Algorithm)을 사용하여 간선의 가중치가 작은 것부터 선택
   • 유니온-파인드(Union-Find) 자료구조를 사용하여 사이클을 방지
   • 시간 복잡도: O(E log E) (간선 정렬이 주요 연산)

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

   class Graph: def __init__(self, vertices): self.V = vertices self.edges = [] def add_edge(self, u, v, weight): self.edges.append((weight, u, v)) def find(self, parent, i): if parent[i] == i: return i return self.find(parent, parent[i]) def union(self, parent, rank, x, y): root_x = self.find(parent, x) root_y = self.find(parent, y) if rank[root_x] < rank[root_y]: parent[root_x] = root_y elif rank[root_x] > rank[root_y]: parent[root_y] = root_x else: parent[root_y] = root_x rank[root_x] += 1 def kruskal_mst(self): self.edges.sort() parent = {i: i for i in range(self.V)} rank = {i: 0 for i in range(self.V)} mst = [] for weight, u, v in self.edges: root_u = self.find(parent, u) root_v = self.find(parent, v) if root_u != root_v: self.union(parent, rank, root_u, root_v) mst.append((u, v, weight)) return mst g = Graph(4) g.add_edge(0, 1, 4) g.add_edge(0, 2, 2) g.add_edge(1, 3, 3) g.add_edge(2, 3, 1) mst = g.kruskal_mst() print(mst) # 최소 스패닝 트리 출력

   ✅ 출력 예시

   1	[(2, 3, 1), (0, 2, 2), (1, 3, 3)]

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

   • 하나의 정점에서 시작하여, 연결된 최소 가중치의 간선을 추가하면서 MST를 생성
   • 힙(Heap) 또는 우선순위 큐(Priority Queue)를 사용하여 최적의 간선을 선택
   • 시간 복잡도: O(E log V) (우선순위 큐 활용 시)

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

   import heapq def prim_mst(graph, start): mst = [] visited = set() min_heap = [(0, start, None)] while min_heap: weight, current, prev = heapq.heappop(min_heap) if current not in visited: visited.add(current) if prev is not None: mst.append((prev, current, weight)) for neighbor, edge_weight in graph[current]: if neighbor not in visited: heapq.heappush(min_heap, (edge_weight, neighbor, current)) return mst graph = { 'A': [('B', 4), ('C', 2)], 'B': [('A', 4), ('D', 3)], 'C': [('A', 2), ('D', 1)], 'D': [('B', 3), ('C', 1)] } mst = prim_mst(graph, 'A') print(mst) # 최소 스패닝 트리 출력

   ✅ 출력 예시

   1	[('A', 'C', 2), ('C', 'D', 1), ('D', 'B', 3)]

신장 트리 구현 예시

최소 신장 트리를 이용한 네트워크 설계

도시들을 연결하는 최소 비용의 통신망을 설계하는 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 도시 간 연결 비용을 나타내는 그래프
cities = ["Seoul", "Busan", "Daegu", "Incheon", "Gwangju", "Daejeon", "Ulsan"]
n = len(cities)

# 도시 간 거리(비용) 행렬
distances = [
    [0, 325, 237, 27, 268, 140, 295],
    [325, 0, 88, 352, 270, 200, 60],
    [237, 88, 0, 264, 192, 122, 76],
    [27, 352, 264, 0, 295, 167, 322],
    [268, 270, 192, 295, 0, 141, 253],
    [140, 200, 122, 167, 141, 0, 189],
    [295, 60, 76, 322, 253, 189, 0]
]

# 인접 리스트 형태로 변환
graph = [[] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i != j:
            graph[i].append((j, distances[i][j]))

# 크루스칼 알고리즘으로 MST 찾기
mst_edges, total_cost = kruskal_mst(graph)

# 결과 출력
print("최소 비용 통신망:")
for u, v, weight in mst_edges:
    print(f"{cities[u]} -- {cities[v]}: {weight}km")
print(f"총 케이블 길이: {total_cost}km")

클러스터링을 위한 MST 기반 알고리즘

데이터 포인트 간의 거리를 기반으로 클러스터를 식별하는 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

import numpy as np
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt

# 데이터 생성
X, y = make_blobs(n_samples=300, centers=4, random_state=42)

# 거리 행렬 계산
n = len(X)
distance_matrix = np.zeros((n, n))
for i in range(n):
    for j in range(i+1, n):
        dist = np.sqrt(np.sum((X[i] - X[j])**2))
        distance_matrix[i][j] = dist
        distance_matrix[j][i] = dist

# 인접 리스트 생성
graph = [[] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i != j:
            graph[i].append((j, distance_matrix[i][j]))

# MST 계산
mst_edges, _ = kruskal_mst(graph)

# 클러스터링: MST에서 가장 긴 간선 k-1개 제거하여 k개의 클러스터 생성
k = 4  # 클러스터 수
mst_edges.sort(key=lambda x: x[2], reverse=True)
edges_to_remove = mst_edges[:k-1]

# 클러스터 계산
parent = list(range(n))

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    parent[find(x)] = find(y)

# 모든 MST 간선 연결
for u, v, _ in mst_edges:
    union(u, v)

# 가장 긴 간선 k-1개 제거
for u, v, _ in edges_to_remove:
    parent[find(u)] = u
    parent[find(v)] = v

# 클러스터 라벨 할당
clusters = [find(i) for i in range(n)]

# 시각화
plt.figure(figsize=(10, 6))
plt.scatter(X[:, 0], X[:, 1], c=clusters, cmap='viridis')
plt.title('MST 기반 클러스터링')
plt.show()

신장 트리의 구현과 최적화

1. 자료구조 선택
   신장 트리 알고리즘의 효율성은 사용하는 자료구조에 크게 영향을 받는다:

   • Union-Find: 크루스칼 알고리즘에서 사이클 탐지에 필수적
   • 우선순위 큐: 프림 알고리즘에서 최소 가중치 간선 선택
   • 인접 리스트/행렬: 그래프 표현 방식에 따른 성능 차이

2. 병렬 구현
   대규모 그래프에서는 알고리즘의 병렬 구현이 중요하다:

   • 보로프카 알고리즘: 본질적으로 병렬 처리에 적합
   • 분할 정복 MST: 그래프를 분할하여 병렬 처리 후 결과 병합

3. 근사 알고리즘
   초대형 그래프에서는 정확한 MST를 구하기 어려울 수 있어 근사 알고리즘을 사용한다:

   • 랜덤 샘플링: 간선의 일부만 샘플링하여 MST 근사
   • 로컬 검색: 초기 해를 점진적으로 개선

스패닝 트리의 활용

1. 네트워크 구축
   • 최소 비용으로 인터넷 또는 전화망 구축
2. 전력망 설계
   • 최소 비용으로 송전망 연결
3. 도로 및 철도 건설
   • 최소 비용으로 모든 도시 연결
4. 클러스터링(Clustering)
   • 데이터 그룹화를 위한 스패닝 트리 활용
5. 컴퓨터 그래픽스
   • 모델링에서 최소한의 연결 구조 유지

스패닝 트리 vs. 최소 스패닝 트리 비교

참고 및 출처