♟ 최소 신장 트리(MST)와 대표 알고리즘, 크루스칼 vs 프림 비교 분석

관련글 :

유니온 파인드	https://waydd.tistory.com/29
인접 리스트, 인접 행렬	https://waydd.tistory.com/94
크루스칼 + 유니온-파인드	https://waydd.tistory.com/143

 

 

1. 최소 신장 트리(MST) 란?

 

그래프의 모든 정점을 최소 비용으로 연결하는 트리

• 혹은 최소 스패닝 트리
• 그래프(정점 N개) 에서 간선 N-1개만 남겨서 트리처럼 만든 것
  → 하나의 그래프(연결 그래프 G)에서 모든 정점을 포함(연결)하고 사이클(고리) 없이 이어지게 만든 트리 모양의 부분 그래프
• 가중치가 같아도 MST는 유일하지 않을 수 있음
• 무방향 그래프, 연결 그래프, 사이클 ❌, 가중치 있음
  → 자가 루프도 MST에서는 필요 없는 간선 (아래 알고리즘으로 무시 가능)

※ 트리 vs 신장 트리
- 트리 : 사이클이 없는 연결 그래프, 일반적인 자료구조, 계층적 구조를 가짐
- 신장 트리 : 그래프 내에서만 정의됨, 즉 그래프 내부에서 간선을 추려 만든 트리

※ 최소 스패닝 트리
- Spanning Tree : 그래프의 모든 정점을 포함하고 사이클이 없는 트리
- Minimum Spanning Tree : 가능한 모든 Spanning Tree 중에서 간선 가중치 합이 최소인 트리

 

 

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

 

간선을 하나씩 선택하며 항상 최소 비용 간선부터 선택하는 알고리즘 (간선 중심)

• 가장 싼 간선부터 차례대로 넣되, 사이클은 제외 → 최소 비용 보장 (증명 : 탐욕적 선택 속성 + MST의 최적 부분 구조)
• 탐욕법(가중치 낮은 간선 선택) 이기 때문에 시작 단계에서 간선 가중치 기준으로 오름차순 정렬
• 유니온-파인드(Disjoint Set) 사용
  → 각 간선을 선택할 때 그 간선을 추가했을 때 사이클(순환 구조)이 생기는지 확인 하기 위함
• 간선 위주의 처리에 효율적, 반대로 정점 수 많고 간선이 밀집되면 느림
  → 희소 그래프(간선 적음) 에 유리
• 간선 리스트(Edge List) 필요
• 통신망 구축 문제 에 사용
• 시간복잡도 : O(E log E) (간선 정렬 + 유니온 파인드)

※ 간선 리스트란?
  edges = [(0, 1), (0, 2), (1, 2), (2, 3)]  # 무방향 그래프
  edges = [(0, 1, 5), (0, 2, 3), (2, 3, 2)]  # 가중치가 있는 방향 그래프
- 그래프의 모든 간선(edge)을 하나씩 나열한 리스트
- 간선은 보통 (시작 정점, 도착 정점) 혹은 (시작, 도착, 가중치) 형태로 표현됨
- 이웃 정점 탐색 시 비효율적 (O(E))

※ 희소 그래프란?
- 간선(edge) 수가 정점(vertex) 수에 비해 상대적으로 적은 그래프
- 주로 인접 리스트를 사용해 표현됨 ( = 연결된 정보만 기록 → 공간 절약, 메모리 효율적  )
- 반대는 조밀 그래프 (간선 수가 많음)로, 주로 인접 행렬을 사용해서 표현(시간복잡도 낮기 때문)

 

- 예시 코드

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

def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

def kruskal(n, edges):
    parent = [i for i in range(n)]
    edges.sort(key=lambda x: x[2])  # 가중치 기준 정렬
    total = 0
    edge_count = 0  # ➕ 간선 개수 카운트 추가
    
    for a, b, cost in edges:
        if find(parent, a) != find(parent, b):
            union(parent, a, b)
            total += cost  # 누적된 간선 비용이 최소 신장 트리의 비용
            edge_count += 1                     # ➕ 간선 수 증가
            
            if edge_count == n - 1:             # ➕ 모든 정점을 연결했다면 종료 (명시적, 최적화)
                break
    return total

※ 단계별 설명
①  모든 간선을 비용 기준 정렬 (가장 짧은 간선부터 하나씩 추가하기 위함) → costs.sort(key=lambda x: x[2])
→→ 그리디(Greedy) 전략
② 유니온-파인드를 위한 부모 배열 초기화 → parent = [i for i in range(n)]
③ 가장 비용이 낮은 간선부터 하나씩 꺼내기 → for a, b, cost in costs:
④ 두 정점이 서로 다른 집합인지 확인 (사이클 방지) → if find(parent, a) != find(parent, b):
⑤ 위를 만족하면 MST에 포함시키고 병합 → union(parent, a, b)
⑥ 사이클을 피하면서 n-1개의 간선을 선택
⑦  MST에 모든 정점이 포함될 때 (n-1개의 간선 연결될 때)까지 반복 → if edge_count == n - 1:
⑧  누적된 간선 비용이 MST의 총 비용 (total)

 

 

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

 

하나의 정점에서 시작해서 가까운 정점으로 확장 하는 알고리즘 (정점 중심)

• MST 집합에 포함된 정점에서 가장 작은 비용 간선 선택
• 우선순위 큐(heap) 사용
  → (가중치, 노드) 저장
  → 현재까지 연결된 정점에서 가장 가중치 작은 간선 선택
• 사이클 방지 위해 방문 체크 필요 (이미 포함된 정점은 스킵)
• 정점 기반 처리에 효율적 →  조밀 그래프(간선이 많음) 에 유리
• 인접 리스트, 인접 행렬 필요 
• 시간 복잡도 : O(E log V) ≈ O(V² log V) (heap + 인접 리스트 방식)
  O(V²) (인접 행렬 + 단순 반복문)  조밀 그래프 일땐 인접 리스트 방식보다 빠름

 

- 예시 코드

import heapq

def prim(start, graph, n):
    visited = [False] * n  # 방문 여부
    pq = [(0, start)]  # (가중치, 정점)
    total = 0

    while pq:
        cost, node = heapq.heappop(pq)  
        if visited[node]:
            continue
        visited[node] = True 
        total += cost  
        for next_cost, next_node in graph[node]:
            if not visited[next_node]:  # MST에 아직 포함되지 않은 정점만
                heapq.heappush(pq, (next_cost, next_node))  # 해당 정점과 연결된 간선을 모두 큐에 넣음
                                                            # 새로운 정점을 탐색 대상으로 추가 → MST를 점진적으로 확장
    return total

※ 단계별 설명
①  아무 정점 하나를 시작점으로 선택 → pq = [(0, start)]
②  해당 정점과 연결된 간선을 모두 우선순위 큐에 넣음 → heapq.heappush(pq, (next_cost, next_node))
③  우선순위 큐에서 가중치가 가장 작은 간선을 꺼냄(선택) → cost, node = heapq.heappop(pq)
④ 현재 정점을 MST에 포함시킴 → visited[node] = True
⑤ 그 간선으로 연결된 정점으로 확장 → for next_cost, next_node in adj[node]:
⑥  연결된 정점이 아직 MST에 포함되지 않았다면 추가 → if not visited[next_node]: heapq.heappush(...)
⑦  MST에 모든 정점이 포함될 때 (= 모든 정점이 연결될 때)까지 반복 → pq가 비어있을때 종료
⑧  누적된 간선 비용이 최소 신장 트리의 비용 (total)