최소 스패닝 트리(MST)

1. 정의

무방향 그래프 G(V,E)에서 E에 속한 간선들로 사이클을 포함하지 않으면서 모든 정점 V를 연결한 부분 그래프를 신장 트리

조건

• 간선의 개수는 n-1개 (최소 간선)
• 사이클을 이루지 않는다 (최소 스패닝 "트리")
• 간선들의 가중치 합이 최소("최소" 스패닝 트리)

2. 활용

효율적인 통신 망 설계 등에 이용

3. 구현 방법

크루스칼(Kruskal)

모든 간선을 가중치 기준으로 오름차순 정렬하고 이 간선들을 순서대로 모든 정점이 연결될 때까지 연결

알고리즘

• Greedy
• Union & Find

시간 복잡도

O(ElogE)

프림(Prim)

임의의 시작점에서 현재까지 연결된 정점들에서 연결되지 않은 정점들에 대해, 가장 가중치가 작은 정점을 연결하는 정점 선택 기반으로 동작

알고리즘

• Priority Queue
• 다익스트라 알고리즘과 구현 방식 유사

시간 복잡도
O(ElogV)

그래프 내의 간선이 많은 경우는 프림 알고리즘,
간선이 적은 경우는 크루스칼 알고리즘이 유리