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

MST

하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하다. 최소 길이의 간선으로 모든 노드들을 연결해야 되는 문제가 나올 때 최소 신장 트리 알고리즘을 사용 할 수 있다.

Kruskal Algorithm

크루스칼 알고리즘은 대표 적인 최소 신장 트리 알고리즘이다. 크루스칼 알고리즘은 greedy algorithm(탐욕 기법)에 속한다. 먼저 모든 간선에 대하여 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함시키면 된다.  Kruskal 알고리즘은 간선을 정렬하는데 시간이 가장 오래 걸리기 때문에 간선의 개수가 E 일때, O(ElogE)의 시간 복잡도를 가진다.

(1) 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
(2) 간선을 하나씩 확인하며 현재의 간선이 cycle을 발생시키는지 확인한다.
Ⅰ. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
Ⅱ. 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
(3) 모든 간선에 대하여 (2)번의 과정을 반복한다.

 

* tree와 graph의 차이

	그래프	트리
방향성	방향 그래프 혹은 무방향 그래프	방향 그래프
순환성	순환 및 비순환	비순환
루트 노드 존재 여부	루트 노드가 없음	루트 노드가 존재
노드 간 관계성	부모와 자식 관계 없음	부모와 자식 관계
모델의 종류	네트워크 모델	계층 모델