최소 스패닝 트리(MST, Minimum Spanning Tree)

Spannig Tree

그래프 내의 모든 정점을 포함하는 트리

위의 정의에 따라 $N$개의 정점을 가지고 있는 그래프를 $N-1$개의 간선으로 연결하였다면 이는 트리의 형태가 되며 Spanning Tree 의 정의를 만족한다.

Minimum Spanning Tree

Spanning Tree 중 사용한 간선들의 가중치의 합이 최소인 트리

Spanning Tree 와 MST 는 하나의 그래프에 여러 개가 존재할 수 있다. 이러한 MST 를 구하는 알고리즘에는 2가지 방식이 있다. Prim 과 Kruskal 알고리즘이다.

Prim

정점을 선택하며 진행되는 알고리즘이며, 하나의 집합에 계속해서 포함시키는 방식으로 진행된다.

1. 시작 정점을 집합$(S)$에 포함시킨다.
2. $S$에서 인접한 정점들 중에서 갈 수 있는 모든 정점들 중에 가중치가 최소인 간선으로 이어져 있는 정점을 선택하여 $S$에 포함시킨다.
3. 2번을 모든 정점을 포함시킬 때까지 반복한다.

인접 정점의 최소 가중치 간선은 priority queue(우선 순위 큐) 를 통해 구현할 수 있다. 시간복잡도는 $O(ElogV)$가 된다.

Kruskal

간선을 선택하며 진행되는 알고리즘이다.

1. 간선을 가중치를 기준으로 오름차순으로 정렬한다.
2. 가중치가 낮은 간선부터 선택한다.
   2-1. 해당 간선에 이어진 정점 2개를 집합에 추가했을 때 사이클을 이루는지 판단한다.
   2-2. 사이클을 이룬다면 해당 간선을 포함하지 않는다. 이루지 않는다면 해당 간선을 포함시키고 해당 정점들을 집합에 추가한다.
3. 2번을 모든 간선에 대해 반복한다.

사이클을 이루는지의 여부는 Union Find 를 통해 구현할 수 있다. 시간복잡도는 $O(ElogE)$가 된다.

연습용 문제(BOJ 1197번: 최소 스패닝 트리)