For a better world

최소 비용 신장 트리의 특징

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

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

• 크루스칼(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/프림_알고리즘