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

최소 신장 트리란

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

핵심 개념

신장 트리의 조건

1. 모든 정점 포함: 그래프의 모든 정점이 트리에 포함되어야 함
2. 연결성 유지: 모든 정점이 연결되어 있어야 함
3. 사이클 없음: 트리 구조이므로 사이클이 존재하지 않음
4. 간선 개수: V개의 정점을 가진 그래프의 신장 트리는 정확히 V-1개의 간선을 가짐

최소 신장 트리의 특징

시각적 예시

다음과 같은 그래프가 있을 때:

     (A)
    2/ \3
   (B) (C)
    1\ /4
     (D)

간선 목록: A-B(2), A-C(3), B-D(1), C-D(4)

가능한 신장 트리들:

• [A-B, A-C, B-D] → 가중치 합: 2+3+1 = 6 ✓ (최소)
• [A-B, A-C, C-D] → 가중치 합: 2+3+4 = 9
• [A-B, B-D, C-D] → 가중치 합: 2+1+4 = 7
• [A-C, B-D, C-D] → 가중치 합: 3+1+4 = 8

최소 신장 트리: [A-B, A-C, B-D], 가중치 합 = 6

주요 알고리즘

최소 신장 트리를 구하는 대표적인 알고리즘은 크게 두 가지가 있다:

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

각 알고리즘의 상세한 설명은 해당 페이지에서 확인할 수 있다.

알고리즘 비교

주의사항

• 그래프가 연결되어 있어야 MST가 존재함
• 연결되지 않은 그래프에서는 최소 신장 포레스트(여러 개의 트리)가 생성됨
• 간선 가중치가 동일한 경우 MST가 여러 개 존재할 수 있음
• 최소 비용은 항상 동일하지만, 선택되는 간선 집합은 다를 수 있음
• 방향 그래프에서는 MST가 아닌 최소 신장 아보레센스(arborescence)를 사용