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

신장 트리 (Spanning Tree) 란?

- 그래프 내의 모든 정점을 포함하는 트리

- 사이클이 형성되지 않도록 모든 정점이 연결된 트리

- 최소 연결 부분 그래프로 N개의 정점, N-1개의 간선을 가진다.

 

[예시]

해당 그래프에서 다음과 같은 신장 트리를 구할 수 있다.

 

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

- 주어진 그래프에서 최소한의 비용으로 만든 트리

- 간선 가중치의 합이 최소인 스패닝 트리

- 통신망, 도로망, 유통망 구축 비용 등에 활용

 

MST 구현 방법

- 크루스칼 알고리즘 (Kruskal's Algorithm)

- 프림 알고리즘 (Prim's Algorithm)

 

# 크루스칼 알고리즘 (Kruskal's Algorithm)

- 탐욕적 방법을 이용하여 최적의 해답을 구하는 알고리즘

- MST의 특징에 근거하여, 각 단계에서 사이클을 이루지 않는 최소 비용 간선 선택

- 디스조인트셋 (disjoint Set) 을 활용

- 희소 그래프 일 경우 적합한 기법

- 시간 복잡도 : O($E\log E$)

 

[구현 방법]

- 그래프의 간선 가중치를 기준으로 오름차순 정렬
- 결과로 반환할 MST 집합은 공집합으로 초기화
- 정렬된 순서대로 사이클을 형성하지 않는 간선 선택
  (단, 가장 낮은 가중치 우선 선택하되, 사이클 형성하는 간선 제외.)
- 선택한 간선 MST 집합에 추가
- 모든 엣지에 대한 연산 수행

[사이클 생성 확인]

- 간선이 같은 집합에 속해 있는지 확인
- Union-Find 알고리즘 이용 (동일한 집합일 경우, 루트 노드가 같다.)

 

 

# 프림 알고리즘

- 가장 작은 가중치의 엣지를 시작점으로 하여 집합을 단계적으로 확장하는 알고리즘

- 정점 기준 선택

- 밀집 그래프 일 경우 적합한 기법

- 시간 복잡도 : O($V^{2}$), O($E\log V$)

 

[구현 방법]

- MST 집합에 시작 정점만 포함
- 이전 단계에서 생성된 MST 집합에 인접한 정점 중 최소 값으로 연결된 정점 선택
- N-1개의 간선을 가질 때 까지 반복 수행

 

[관련 문제]

https://www.acmicpc.net/problem/1197

https://www.acmicpc.net/problem/1922

https://www.acmicpc.net/problem/15481

 

[참고]

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

https://ratsgo.github.io/data%20structure&algorithm/2017/11/28/MST/