🌿 최소 신장 트리 (MST, Minimum Spanning Tree) 완전 정리

---

✅ MST란?

최소 신장 트리(Minimum Spanning Tree)는
무방향 가중치 그래프에서 모든 정점을 연결하면서, 간선의 가중치 합이 최소인 트리를 말한다.

조건	설명
연결	모든 정점이 연결되어 있어야 한다
사이클 없음	트리이므로 사이클이 존재하지 않아야 한다
최소 비용	간선 가중치의 합이 최소여야 한다

왜 알고리즘? 이라고 썼냐면... MTS 자체는 알고리즘은 아니다.

항목	분류
크루스칼 / 프림	알고리즘
유니온 파인드	자료구조
MST 결과	트리 구조의 해답 (출력값)
그래프 자체	자료구조

---

✅ MST 특징

• 정점이 V개일 때, 간선은 항상 V - 1개
• 간선 가중치가 작을수록 우선 연결
• 대표 알고리즘: 크루스칼 / 프림

---

✅ 크루스칼 알고리즘 (Kruskal)

✔️ 개념

• 간선을 가중치 기준으로 오름차순 정렬
• 사이클이 생기지 않도록 가장 가중치가 작은 간선부터 선택
• 유니온 파인드로 사이클 여부 판별

✔️ 구현 (Python)

# 유니온 파인드

# parent[x]는 "x의 부모 노드(대표자)"를 저장, 처음에는 각 노드가 자기 자신이 부모: parent[x] = x
# 트리를 구성하되, 루트는 항상 대표로 유지, find(x)는 x의 루트(대표자)를 찾는 함수
# x가 루트가 아니라면 → x의 조상 노드를 재귀로 찾고,찾은 루트를 바로 x의 부모로 저장

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 경로 압축 (path compression)
    return parent[x]

def union(a, b):
    a_root = find(a)
    b_root = find(b)
    if a_root == b_root: 
        return False #이미 같은 집합이라면 False
    parent[b_root] = a_root # b의 대표를 a로 통일
    return True

# 가중치가 있는 간선들의 모음(cost, node1, node2)
edges = [(1, 0, 1), (2, 0, 2), (3, 1, 2), (4, 1, 3), (5, 2, 3)]
edges.sort()  # 가중치 기준 정렬

n = 4
parent = [i for i in range(n)] # 문자열일 때는 다르게 초기화 해야할 듯
total = 0

for cost, a, b in edges:
    if union(a, b):
        total += cost

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

---

✅ 프림 알고리즘 (Prim)

✔️ 개념

• 하나의 정점에서 시작해서, 가장 가까운(가중치가 작은) 간선을 하나씩 선택
• 우선순위 큐(PriorityQueue 또는 heapq)를 사용
• 방문하지 않은 정점 중에서 최소 비용 간선을 선택해 확장

✔️ 구현 (Python)

import heapq

graph = {
    0: [(1, 1), (2, 2)],
    1: [(0, 1), (2, 3), (3, 4)],
    2: [(0, 2), (1, 3), (3, 5)],
    3: [(1, 4), (2, 5)]
}

n = 4
visited = [False] * n
heap = [(0, 0)]  # (비용, 시작 노드)
total = 0

while heap:
    cost, node = heapq.heappop(heap)
    if visited[node]:
        continue
    visited[node] = True
    total += cost
    for next_node, weight in graph[node]:
        if not visited[next_node]:
            heapq.heappush(heap, (weight, next_node))

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

---

✅ 크루스칼 vs 프림 비교

항목	크루스칼	프림
구현 중심	간선 정렬 + 유니온 파인드	우선순위 큐 (heap)
핵심 구조	간선 중심	정점 중심
성능	희소 그래프에 유리	밀집 그래프에 유리
사이클 확인	유니온 파인드 사용	방문 배열 사용

---

✅ 시간 복잡도

알고리즘	시간 복잡도
크루스칼	O(E log E) (간선 정렬)
프림	O(E log V) (heap 사용)

---

🎯 마무리 요약

• MST는 모든 정점을 최소 비용으로 연결하는 트리 구조
• 크루스칼은 간선 정렬 + 유니온 파인드, 프림은 우선순위 큐 + 방문 처리
• 둘 다 탐욕 알고리즘(Greedy Algorithm) 기반이며,
• MST는 네트워크 설계, 최소 연결 비용 문제 등에서 자주 등장한다