[최소 신장 트리(MST, Minimum Spanning Tree)]

신장트리(Minimum Spanning Tree, MST)

그래프가 모든 노드를 포함하고 모든 노드가 연결 되어있으며 Tree의 속성을 만족하는 그래프를 말한다.

그림1.신장 트리의 예

 

최소신장트리(Minimum Spanning Tree, MST)

신장트리 가운데 가중치의 합이 최소인 경우를 신장 트리라고 한다.

 

 

그림2.신장트리와 최소신장트리의 차이

 

이런 MST를 찾아내는 기법이 크게 두 가지가 있다.

 

 

크루스칼 알고리즘(Kruskal’s algorithm)

간선을 오름차순으로 정렬하여, 사이클이 만들어 질 경우를 제외하고 추가하는 방식

 디스조인트 셋(disjoint set)을 기본 자료구조로 활용한다.

 

크루스칼 알고리즘의 시간 복잡도는 O(ElogV)이다.

 

 

 디스조인트 셋(disjoint set)관련해서는 다음 포스팅에서 기재하겠다.

 

프림 알고리즘(Prim Algorithm)

한 정점을 기준으로  가중치가 가장 작은 엣지를 하나 뽑고 이 엣지에 연결된 노드와 해당 엣지를 추가하며 점진적으로 해결하는 방식

0. 임의의 정점을 선택하여 비어있는 T에 포함시킨다. (이제 T는 노드가 한 개인 트리. )

1. T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

2. 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다. 

                (step 1에서 찾은 간선도 같이 T에 포함됩니다.)

3. 모든 노드가 T 에 포함될 때 까지, 1,2 를 반복한다.

 

 

 

 

인접 행렬과 최소 비용값들이 들어가 있는 배열 내에서 최소 비용값을 찾는 검색을 사용할 경우, 시간 복잡도는 O(V^2)가 된다. 이진 힙 자료 구조와 인접 리스트 표현을 사용한다면, 프림 알고리즘은 시간 복잡도는 O(ElogV)이다.

 

 

 

 

출처

그림1:위키백과

그림2:https://ratsgo.github.io/data%20structure&algorithm/2017/11/28/MST/