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

최소 신장 트리 (Minimum Spanning Tree)

• 주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리

(a) 주어진 가중치 그래프

좌측부터 (b), (c), (d)

• (b)는 최소 신장 트리
• (c)는 가중치의 합이 (b)보다 큼
• (d)는 트리가 주어진 그래프의 모든 노드를 포함하지 않음

Idea

• 사이클이 없도록 모든 점을 연결
• 그래프의 점의 수가 n인 경우 신장 트리에 (n - 1)개의 선분이 존재
  • 트리에 선분을 하나 추가할 경우, 반드시 사이클이 형성

관련 알고리즘

• 크러스컬 (Kruskal) 알고리즘
  • 가중치가 가장 작은 선분이 사이클을 만들지 않을 때만 그리디하게 선분 추가
  • 2024.03.10 - [Algorithm] - [알고리즘] 크러스컬 최소 신장 트리 (Kruskal MST)

• 프림 (Prim) 알고리즘
  • 임의의 점 하나를 선택한 후, (n - 1)개의 선분을 하나씩 추가시켜 트리 제작
  • 2024.03.11 - [Algorithm] - [알고리즘] 프림 최소 신장 트리 (Prim MST)