[알고리즘] 최소 신장 트리(Minimum Spanning Tree)

💡최소 신장 트리란?

신장 트리(Spanning Tree)

• 그래프의 모든 정점을 포함하는 최소 연결 부분 그래프
• 트리의 특징
  • 정점의 개수 n 개인 신장 트리의 간선 개수는 n-1 개
  • 모든 정점이 연결
  • 사이클 없음
  • 임의의 두 정점을 선택했을 때, 그 사이 경로는 유일함

예시

위 그래프에 대한 아래 신장 트리 예시들

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

• 신장 트리 중 간선 가중치 합이 최소인 신장 트리

예시

위 그래프에 대해 최소 신장 트리

💡최소 신장 트리 알고리즘

1. 크루스칼(Kruskal) 알고리즘

• 그리디를 이용하여 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 방법
  • 간선을 중심으로 하는 알고리즘
  • greedy하게 간선을 선택하는 방법
• 과정
  1. 간선 가중치를 기준으로 오름차순 정렬
  2. 간선 리스트 중 작은 것부터 선택하면서 사이클을 형성하지 않는다면 집합에 추가

2. 프림(Prim) 알고리즘

• 시작 정점에서 출발하여 신장 트리 집합을 단계적으로 확장하는 방법
  • 정점을 중심으로 하는 알고리즘
  • 이전 단계의 신장 트리를 확장하는 방법
• 과정
  1. 시작 단계에서 시작 정점을 MST 집합에 포함
  2. 앞 단계에서 만들어진 MST 집합의 정점 중 최소 간선으로 연결된 정점 선택하여 트리 확장
  3. 트리가 N-1 간선을 가질 때까지 반복