최소 신장 트리(MST) - Kruskal 알고리즘 / Prim 알고리즘

신장 트리 

그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

N개의 정점으로 이루어진 무향 그래프에서 N개의 정점과 N-1개의 간선으로 이루어진 트리

 

---

최소 신장 트리 

무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장트리

특징

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

---

Prim 알고리즘 

정점 중심 

1. 임의의 한 정점을 선택

2. 선택한 정점과 인접한 정점 중에 최소 비용 간선이 존재하는 정점을 선택

3. n-1번 반복

 

 

---

Kruskal 알고리즘

간선 중심

1. 모든 간선을 가중치에 따라 오름차순 정렬

2. 가중치가 낮은 간선부터 선택하여 트리를 증가시킴 - 사이클이 발생하면 그 다음 간선을 선택

3. n-1번 반복

 

---

출처

https://pyrite-emu-d92.notion.site/c1824e4ad68c46948dc235f160f68392

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