Algorithm, MST(최소 신장 트리)

Spanning Tree

• 그래프 내의 모든 정점을 포함 하는 트리
• 그래프에서 일부 간선을 선택해서 만든 트리

  Spanning Tree 특징

  

• DFS,BFS 를 이용하여 그래프에서 신장 트리를 찾을 수 있다.
• 하나의 그래프에는 많은 신장 트리가 존재 할 수 있다.
• 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안된다.

---

MST

MST란

• Minimum Spanning Tree 최소 신장 트리
• 네트워크 (가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결 하는 것이다.
• 최소 신장 트리는 최단거리가 아닐수있다 (최단 경로는 다익스트라 이용)

MST의 특징

1. 간선의 가중치 합이 최소여야 한다.
2. 사이클이 포함되어서는 안된다.
3. n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.

---

MST의 구현 방법

1. Kruskal MST 알고리즘

• 탐욕적인 방법을 이용하여 네트워크의 모든 정점을 최소 비용으로 연결하여 최적 해답을 구하는 것
• 모든 간선의 가중치를 조사하고 정렬 후 순서대로 연결해 나가는 방식

[동작]

1. 그래프의 간선들을 가중치의 오름차순으로 정렬 한다
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
   • 즉, 가장 낮은 가중치를 먼저 선택
   • 사이클을 형성하는 간선은 제외 (union-find 알고리즘 이용)
3. 해당 간선의 현재 MST의 집합에 추가한다.

2. Prim MST 알고리즘

• 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법
• 정점에 연결 된 간선의 가중치 중 가장 작은 가중치의 간선을 연결해 나가는 방식

[동작]

1. 시작 단계에서 시작 정점만이 MST집합에 포함된다.
2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선을 연결된 정점을 선택하여 트리를 확장한다.
   • 즉, 가장 낮은 가중치를 먼저 선택한다.
3. 위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복한다.

정리

• kruskal : 그래프에 간선지 적게 존재 하는 ‘희소 그래프’의 경우 적합
• prim : 그래프에 간선이 많이 존재 하는 ‘밀집 그래프’의 경우 적합

---

Reference

• [참고] : https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html
• [union-find] : https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

• https://www.zerocho.com/category/Algorithm/post/584bcd42580277001862f1a7