최소 신장 트리(Minimum Spanning Tree)

그래프에서 최소 비용 문제

• 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리
• 두 정점 사이의 최소 비용의 경로 찾기

 

신장 트리

신장 트리는 N개의 정점으로 이루어진 연결 그래프에서 N개의 정점과 N-1개의 간선으로 이루어진 트리입니다.

즉, N-1개의 간선으로 "모든 정점들이 연결"되어있습니다.

 

당연히 트리이기 때문에 사이클이 존재하면 안됩니다~~

 

최소 신장 트리

무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

 

구하는 알고리즘으로는 "프림"과 "크루스칼"이 있습니다.

 

크루스칼 알고리즘

가중치가 가장 작은 간선이 사이클을 만들지 않을 때에만 그리디하게 간선을 추가시킵니다.

간선의 개수가 M개라고 할 때, 시간 복잡도는

 

가중치로 정렬 : O(MlogM)

간선들을 모두 탐색할 경우(그래프의 모든 간선이 탐색되어야 트리가 완성될 경우) : M

사이클 검사 : O(logM)

즉, MlogM + MlogM = O(MlogM)

 

크루스칼 알고리즘 순서

1. 모든 간선의 가중치를 오름차순으로 정렬합니다

2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 만듭니다.

• 만약 여기서 사이클이 존재하면 continue를 합니다. 사이클 판단은 앞서 Union-Find 연산을 사용하시면 됩니다

3. n-1개의 간선이 선택될 때까지 2번을 반복합니다.

• 왜냐하면 MST는 N개의 정점을 연결하기 위해서 N-1개의 간선이 필요하기 때문입니다.