티스토리 뷰
최소 스패닝 트리(Minimum Spanning Tree)는 무향그래프(Undirected Graph)에서
간선마다 비용이 주어질 때 그 간선들의 비용의 합이 최소인 스패닝 트리입니다.
이 때 여기서 스패닝 트리는 그래프의 정점 전부와 간선의 부분 집합으로
구성된 부분 그래프 중 간선들이 사이클을 이루지 않는 트리를 말합니다.
그러므로 V개의 정점을 가지고 있는 그래프의 스패닝 트리는 모든 정점이 연결되어 있고
정확히 V-1개의 간선으로 연결되어 있어야 합니다.
이를 구하는 두가지 알고리즘이 있으며 아래와 같습니다.
1. 크루스칼 알고리즘
2. 프림 알고리즘
두 알고리즘은 모두 각 단계마다 지금 가장 좋은 방법인 비용이 최소로 드는 방법으로 이동하는
앞서 배운 탐욕법을 사용하여 최소 스패닝 트리를 구하게 됩니다.
크루스칼 알고리즘의 경우 전체 간선을 비용에 따라 오름차순으로 정렬한 뒤
비용이 최소인 간선부터 선택하여 최소 스패닝 트리를 완성 시킵니다.
이 때 이 간선을 선택했을 때 사이클이 생성된다면 선택하지 않고 진행합니다.
서로 이어져 있는 정점들을 집합으로 묶으면 어떤 두 부분집합 사이에도 교집합은 없고 모든 부분집합은 전체 정점이 되므로
앞서 배운 상호베타적 집합을 이용하여 사이클의 생성 여부를 두 정점이 같은 집합에 있는 지로 확인해 볼 수 있습니다.
프림 알고리즘의 경우 다익스트라 알고리즘과 비슷하게
한 정점을 선택하고 시작하여 현재까지 선택된 정점에서 선택되지 않은 정점으로 갈 수 있는 가장 최소 비용의 정점을
모든 정점이 선택될 때까지 진행합니다.
크루스칼 알고리즘의 시간복잡도는 정렬이 시간복잡도를 지배하여 정점 개수가 V 간선 개수가 E일 때 O(ElgE)이며
프림 알고리즘은 우선순위 큐를 사용하여 갈 수 있는 최소의 정점을 빠르게 구한다면 시간복잡도는 O(ElgV)입니다.
그래프의 특성에 맞게 알맞는 알고리즘을 선택하여 구할 수 있습니다.
기본 문제
