[ 알고리즘 ] 최소 신장 트리(MST) / 크루스칼 알고리즘 (Kruskal Algorithm)

신장트리(Spanning Tree)란?

방향성이 없는 그래프의 서브그래프(Subgraph)들 중에서 모든 정점을 연결하는 트리를 말한다. 서브그래프는 주어진 그래프에서 일부 정점과 간선만을 택해서 구성한 새로운 트리를 말한다. 신장 트리는 그래프의 하위 개념이기도 하다.

그래프에서 난데없이 트리?

그래프는 사이클을 형성하는 간선만 제거하면 트리로 변신할 수 있다. 

그래프 vs 트리

그래프

- 정점(Vertex)와 그 노드를 연결하는 간선(Edge)으로 이루어져 있다.

 

트리

- 그래프의 일종

- Cycle을 가지지 않는다.

- 계층적 구조를 가진다.

- 단 하나의 root를 가진다.

최소 신장 트리(Minimum Spanning Tree : MST)란?

최소 가중치 신장 트리(Minimum Weight Spanning Tree)라고도 불린다.

각 간선이 갖고 있는 가중치의 합이 최소가 되는 신장 트리가 바로 최소 신장 트리이다.

한 그래프에서 최소 신장 트리는 하나가 아니라 여러개일 수 있다.

 

 

최소신장트리 알고리즘에는 프림 알고리즘, 크루스칼 알고리즘 두가지가 있다.

 

프림 알고리즘은 정점을 추가하면서 트리를 확장하는 방법이고,
크루스칼 알고리즘은 간선을 추가하면서 최소 신장 트리를 만드는 방법이다.

 

프림은 시작점을 정하고, 시작점에서 가까운 정점 + 최소 비용을 선택하면서 MST를 구성하므로 그 과정에서 사이클을 이루지 않는다.

크루스칼은 시작점을 정하지 않고, 최소 비용의 간선을 차례로 대입하면서 MST를 구성하므로, 그 과정에서 사이클이 이뤄지는지 체크해야한다. 사이클을 확인하는 방법으로는 유니온 파인드(Union-Find)방법이 있다.

 

크루스칼 알고리즘

그래프 내의 모든 간선들의 가중치 정보를 사전에 파악하고 이 정보를 토대로 최소 신장 트리를 구축해나간다.

 

과정은 다음과 같다.

① 간선의 크기를 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택한다.

② 현재 선택한 간선이 정점 u, v를 연결하는 간선일 때, 만약 u와 v가 같은 그룹에 속해있다면 사이클을 만들기 때문에 무시한다. 다른 그룹이라면 같은 그룹으로 포합시키고 현재 선택한 간선을 최소 신장 트리에 추가한다.

③ 최소 신장 트리에 삽입되어 있는 정점들과 이 정점들의 모든 인접 정점 사이에 있는 간선의 가중치를 조사한다.

④ 다음으로 적은 비용의 간선을 선택하고 ②~③을 반복한다. 최소 신장 트리에 V-1개의 간선이 추가되면 과정을 종료한다.