최소 신장 트리

개념

🔷 최소 신장 트리란?

일단 신장 트리(Spanning Tree) 부터 알아야 한다
- 연결 그래프의 모든 정점을 포함하면서, 사이클이 없는 트리 형태의 부분 그래프
- 즉, 모든 정점을 연결하되, 최소한의 간선만 사용한 구조
- 정점이 n개라면 간선은 항상 n - 1개
최소 신장 트리(MST) 란?
- 가능한 모든 신장 트리 중에서 간선 가중치의 합이 최소인 것.

🔹 특징 요약

항목	내용
입력	가중치가 있는 무방향 연결 그래프
조건	모든 정점 연결, 사이클 없음
목표	간선 가중치의 합을 최소화
결과	간선 `n-1`개로 구성된 트리 구조

예시

🔶 원래 그래프

    [A]- 2 -[B]- 3 -[C]
      \      |      /
      (6)   (1)   (5)
        \   /     /
         \ /     /
         [D] ___/
           \
           (4)
             \
             [E]

정점: [A], [B], [C], [D], [E]
간선: 괄호 안 숫자는 가중치(weight)

🔷 최소 신장 트리 (MST)

간선의 가중치 합이 최소이며
모든 정점이 연결됐고 사이클 ❌

       # 최소 신장 트리

    [A]- 2 -[B]- 3 -[C]
             |      
            (1)   
            /     
           /     
         [D]
           \
           (4)
             \
             [E]

선택된 간선: A-B(2), B-D(1), D-E(4), B-C(3)
총 가중치: 2 + 1 + 4 + 3 = 10