그래프 이론 - 5. 최소 신장 트리 (MST, Minimum Spanning Tree)

 

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

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

📌 단계별 실행 과정 (시각화)

📌 입력 그래프

      (0)
     /   \
   1/     \4
   /       \
 (1) ----- (2)
   \       /
   3\     /2
     \   /
      (3)

📌 간선 정렬 후 선택 과정

1. 가중치 1 (0-1) 추가 → MST: {(0-1)}
2. 가중치 2 (2-3) 추가 → MST: {(0-1), (2-3)}
3. 가중치 3 (1-3) 추가 → MST: {(0-1), (2-3), (1-3)}
4. 가중치 4 (0-2) 추가하면 사이클 발생 → 제외

📌 최종 MST

      (0)
     /   
   1/     
   /       
 (1)     (2)
   \     /
   3\   /2
     \ /
      (3)

---

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

📌 단계별 실행 과정 (시각화)

📌 입력 그래프

      (0)
     /   \
   1/     \4
   /       \
 (1) ----- (2)
   \       /
   3\     /2
     \   /
      (3)

📌 정점 확장 과정

1. 시작 정점 (0) 선택 → {0}
2. 가중치 1 (0-1) 추가 → {0, 1}
3. 가중치 3 (1-3) 추가 → {0, 1, 3}
4. 가중치 2 (3-2) 추가 → {0, 1, 3, 2}

📌 최종 MST

      (0)
     /   
   1/     
   /       
 (1)     (2)
   \     /
   3\   /2
     \ /
      (3)

---

📌 더 복잡한 그래프 예제 추가 (8개 정점, 12개 간선)

n = 8
edges = [
    (0, 1, 4), (0, 2, 8), (1, 2, 11), (1, 3, 8),
    (2, 4, 7), (3, 4, 2), (3, 5, 4), (4, 5, 14),
    (4, 6, 9), (5, 6, 10), (6, 7, 2), (7, 0, 1)
]

• 이전보다 정점과 간선 개수가 증가하여 성능 평가 가능
• 크루스칼과 프림 알고리즘을 실행하여 결과 비교

---

📌 크루스칼과 프림의 성능 비교

import time
import random
import heapq

# 크루스칼 알고리즘
def kruskal(n, edges):
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(n)
    mst = []
    
    for u, v, weight in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, weight))
    
    return mst

# 프림 알고리즘
def prim(n, edges):
    graph = {i: [] for i in range(n)}
    for u, v, weight in edges:
        graph[u].append((weight, v))
        graph[v].append((weight, u))

    mst = []
    visited = set()
    pq = [(0, 0)]
    
    while len(visited) < n:
        weight, node = heapq.heappop(pq)
        if node in visited:
            continue
        visited.add(node)
        mst.append((weight, node))
        
        for neighbor_weight, neighbor in graph[node]:
            if neighbor not in visited:
                heapq.heappush(pq, (neighbor_weight, neighbor))
    
    return mst[1:]

# 벤치마크 수행
random.seed(42)
N = 1000  # 정점 개수
E = 5000  # 간선 개수
edges_large = [(random.randint(0, N-1), random.randint(0, N-1), random.randint(1, 100)) for _ in range(E)]

start = time.time()
kruskal(N, edges_large)
print(f"크루스칼 실행 시간: {time.time() - start:.6f}초")

start = time.time()
prim(N, edges_large)
print(f"프림 실행 시간: {time.time() - start:.6f}초")

📌 예상 출력 결과

크루스칼 실행 시간: 0.152003초
프림 실행 시간: 0.085431초

• 프림 알고리즘이 크루스칼보다 빠르게 동작 (간선이 많은 경우)
• 크루스칼은 간선이 적을 때 유리

---

📌 최종 비교표

알고리즘	방식	시간 복잡도	자료구조	장점	단점
크루스칼	간선 중심	𝑂(𝐸 log 𝐸)	유니온 파인드	간선 정렬 후 선택, 사이클 방지	간선이 많으면 성능 저하
프림	정점 중심	𝑂(𝐸 log 𝑁)	우선순위 큐	하나의 정점에서 확장, 간선이 많을 때 유리	초기 정점 선택에 따라 경로 다를 수 있음

📌 언제 크루스칼을 사용해야 하는가?

• 간선이 적은 경우(Sparse Graph, E ≈ N)
• 연결된 여러 개의 컴포넌트에서 MST를 구할 때

📌 언제 프림을 사용해야 하는가?

• 간선이 많은 경우(Dense Graph, E ≈ N²)
• 네트워크 연결 최적화가 필요할 때