[알고리즘] 최소 신장 트리(MST) - 프림, 크루스칼 알고리즘

최소 신장 트리

신장트리

신장 트리(Spanning Tree)란 그래프가 있을 때 모든 정점을 포함하는 트리이다.

N개의 정점이 모두 이어져 있고, N-1개의 간선으로 이루어진다.

기본적으로 트리이므로 사이클이 생겨선 안된다.

 

여러개의 신장트리가 존재 할 수 있다.

최소 신장 트리

최소신장트리(Minimum Spanning Tree)는 신장 트리 중에서 간선에 가중치가 있다고 할 때

가중치의 합이 최소가 되는 신장 트리이다.

언제?

모든 정점을 최소비용으로 연결해야하는 경우

ex) 도로 건설, 전기 회로, 통신 연결(네트워크)관련 문제 

프림,크루스칼 알고리즘

MST를 구하는 대표적인 알고리즘은 프림알고리즘과 크루스칼 알고리즘 두가지가 있다

 

프림 알고리즘

1. 그래프에서 한 정점을 선택해 MST에 추가한다.

2. MST와 인접한 간선 중 최소비용인 간선을 선택한다.

여기서 비용이 1인 간선 선택

여기서 비용이 1인 간선 선택

여기서 비용이 2인 간선 선택

마지막으로 비용 2인 간선 선택

총 비용 : 1+1+2+2+2 = 8

 

프림 알고리즘의 시간 복잡도는 주 반복문이 정점의 수 V만큼 반복하고

내부 반복문이 V번 반복하여 O(V²)이 된다.

 

크루스칼 알고리즘

1. 간선들의 가중치를 오름차순으로 정렬한다.

2. 가중치가 낮은 간선들을 MST에 포함시킨다.
- 단 사이클을 형성하면 제외한다.

1-3 간선 선택

3-4 간선 선택

2-3 간선 선택 (1-2, 2-4 간선은 선택 불가능)

4-6 간선 선택

5-6 간선 선택 , 총 비용 : 1+2+1+2+2 = 8

 

크루스칼 알고리즘의 시간 복잡도는 간선의 개수를 E라고 했을 때 O(ElogE)이 된다.