최소 비용 신장 트리(Minimum Spanning Tree)

최소 비용 신장 트리의 특징

---

• 그래프의 모든 정점이 간선에 의해 하나로 연결되어 있다.
• 그래프 내에서 사이클을 형성하지 않는다.

 

최소 비용 신장 트리의 구성에 사용되는 대표적인 알고리즘

---

• 크루스칼(Kruskal) 알고리즘

가중치를 기준으로 간선을 정렬한 후에 MST가 될 때까지 간선을 하나씩 선택 또는 삭제해 나가는 방식

 

 

• 프림(Prim) 알고리즘

하나의 정점을 시작으로 MST가 될 때까지 트리를 확장해 나가는 방식

 

크루스칼 알고리즘의 핵심

---

오름차순

1. 가중치를 기준으로 간선을 오름차순 정렬
2. 낮은 가중치의 간선부터 시작해서 하나씩 그래프에 추가
3. 사이클을 형성하는 간선을 추가하지 않음
4. 간선의 수가 정점의 수보다 하나 적을 때 MST가 완성

내림차순

1. 가중치를 기준으로 간선을 내림차순으로 정렬
2. 높은 가중치의 간선부터 시작해서 하나씩 그래프에서 제거
3. 두 정점을 연결하는 다른 경로가 없을 경우 해당 간선은 제거하지 않음
4. 간선의 수가 정점의 수보다 하나 적을 때 MST가 완성

크루스칼과 프림 알고리즘 특징

---

크루스칼 알고리즘의 특징

• 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 $O(E\times logV)$의 시간 복잡도를 가진다.

 

프림 알고리즘의 특징

• 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 이진 힙을 이용하여 자료를 처리하였을 때의 기준으로 $O(E\times logV)$의 시간 복잡도를 가진다.
• 그래프가 충분히 빽빽한 경우 $E=\Omega(V\times logV)$에는 피보나치 힙을 이용하여 훨씬 빠르게 할 수 있다.
• 이 방법은 복잡도가 $O(E + V\times logV)$까지 떨어진다.

 

Reference

---

[1] https://ko.wikipedia.org/wiki/크러스컬_알고리즘

[2] https://ko.wikipedia.org/wiki/프림_알고리즘