MST

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

Spanning Tree(신장 트리)란?

• 그래프 내의 모든 정점을 포함하는 트리
• 단, 최소 연결 그래프 형태이다.
• n개의 정점을 가지는 그래프에서 n-1개의 간선으로 연결된 트리이다.
• 하나의 그래프에는 여러 개의 신장트리가 존재한다.

Minimum Spanning Tree(최소 신장 트리)란?

• 신장 트리 중에서 사용된 간선들의 가중치 합이 가장 작은 신장 트리

MST 구현 방법

• 크루스칼(Kruskal)
• 프림(Prim)

크루스칼 (Kruskal)

• 간선을 기준으로 접근한 방법
• 모든 간선을 가중치가 낮은 간선을 우선으로 정렬한 후에
• 가중치가 가장 낮은 간선부터 하나 씩 MST 집합에 추가를 한다
• 이 때, 사이클을 형성하는지 검사를 한다
  • 사이클 형성을 검사하는 방법으로는 Union-Find 알고리즘을 사용한다
• 시간 복잡도 : O(e log e)
  • e 는 간선의 수

프림 (Prim)

• 정점을 기준으로 접근한 방법
• 점진적으로 신장 트리를 확장해 나가는 방식
• 하나의 정점이 가진 간선들 중 가장 가중치가 작은 간선을 선택한다.
  • 하나의 정점이 가진 간선들을 검사해야 하므로 보다 효율적으로 검사하기 위해 힙구조인 우선순위큐를 사용한다
• 이때, 반대편 정점이 이미 사용된 정점인지 검사하여 해당 간선을 선택해도 되는지 확인한다.
• 시간 복잡도 : O(n^2) , 힙 구조를 사용한 경우  O(n log e) 
  • n : 정점의 수, e : 간선의 수

Prim vs Kruskal

그래프 내의 간선의 수가 적은 경우 Kruskal, 그래프 내의 간선이 많은 경우 Prim

참고

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog