[알고리즘] 최소 스패닝 트리_ Kruskal & Prim

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

스패닝 트리란, 그래프에서 순환 없이 모든 정점을 잇는 부분 그래프를 의미한다.

최소 스패닝 트리란, 이러한 스패닝 트리 중에서 간선의 가중치의 합이 가장 작은 스패닝 트리를 의미한다.

이러한 최소 스패닝 트리를 구하는 알고리즘으로 크루스칼(Kruskal)과 프림(Prim) 알고리즘이 있다.

크루스칼 (Kruskal) 알고리즘

크루스칼 알고리즘은 모든 간선 중에서 가장 가중치가 작은 간선부터 연결해 주면서 최소 스패닝 트리를 만드는 알고리즘이다. 간선들을 연결하면서 순환이 발생한다면 해당 간선을 버리고 다음 간선을 선택하게 되는데 이 때, Union-Find 연산을 사용한다.

알고리즘

1. 간선들을 가중치를 기준으로 오름차순으로 정렬한다.
2. 가장 가중치가 작은 간선부터 순서대로 순환을 발생시키지 않는 간선을 고른다.
3. 최소 스패닝 트리에 추가한다.

위 과정에서 간선이 순환을 발생시키는 지를 Union-Find 연산을 사용해서 효과적으로 검사할 수 있다.

프림(Prim) 알고리즘

프림 알고리즘은 시작 정점부터 출발하여 연결된 정점중에 가장 작은 가중치로 연결된 정점을 선택하면서 최소 스패닝 트리를 만드는 알고리즘이다. 간선을 기준으로 하는 크루스칼과 달리 프림은 정점을 기준으로 최소 스패닝 트리를 만드는 알고리즘이다.

알고리즘

1. 시작 정점을 선택하고 최소 스패닝 트리에 추가한다.
2. 연결되어 있는 정점중에 가장 작은 가중치로 연결된 정점을 선택하고, 트리를 확장한다.
3. 2번 과정을 (정점 개수 - 1) 개의 간선을 가질 때까지 반복한다.

크루스칼 VS 프림

어떤 경우에 크루스칼을 쓰고, 프림을 쓸지는 시간 복잡도를 보면 알 수 있다.

크루스칼의 시간 복잡도는 간선을 정렬하는 시간(퀵정렬_ O(logE))과 간선의 개수만큼 연산이 실행(O(E))되기 때문에 O(ElogE)가 된다.

프림의 시간 복잡도는 모든 정점을 우선순위 큐로 확인(O(logV)) 하고, 그 정점들에 대한 간선들을 확인(O(E))하게 되기 때문에 O(ElogV)가 된다.

즉 크루스칼 O(ElogE) vs 프림 O(ElogV)이기 때문에,

간선이 많을 때는 프림, 간선이 적을때는 크루스칼이 더 유리해 보인다.

위 알고리즘을 이용해서 백준 1197번 최소 스패닝 트리를 풀어보았다.

[Algorithm/Java][백준] 1197번 최소 스패닝 트리

[Algorithm/Java][백준] 1197번 최소 스패닝 트리