[알고리즘] 최소비용 신장 트리 (MST)

신장트리

• 신장 트리(spanning tree)란 그래프내의 모든 정점을 포함하는 트리다.
• 신장 트리는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 한다.
• 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다.
• 하나의 그래프에는 많은 신장 트리가 존재 가능하다. 
• 싸이클이 없는 무방향 그래프

 

최소 비용 신장 트리 

최소 비용 신장 트리는 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리를 말한다. 

최소 비용 신장 트리를 구하는 방법으로는 Kruskal과 Prim이 제안한 알고리즘이 대표적으로 사용되고 있으며, 이 알고리즘들은 최소 비용 신장 트리가 간선의 가중치의 합이 최소이어야 하고, 반드시 (n-1)개의 간선만 사용해야 하며, 사이클이 포함되어서는 안 된다는 조건들을 적절히 이용하고 있다. 

 

최소 비용 신장 트리 특징

• 무방향 가중치 그래프.
• 각 엣지에 대하여 가중치가 있다.
• 네트워크 디잔인에 사용

 

알고리즘1 : Generic MST 알고리즘

어떤 MST의 부분집합 A에 대하여 A U {u,v}도 역시 어떤 MST의 부분집합이 될 경우 엣지(u,v)는 A에 대해 안전하다고 한다.

1. 처음에는 A=ø 이다.
2. 집합 A에 대해 안전한 엣지를 찾은 후 이것을 A에 더한다.
3. 엣지의 개수가 n-1개가 될 때 까지 2번을 반복한다.

=> 쉽게 풀어 설명하면 서로 연결된 엣지들을 그룹으로 만들고 그 그룹들을 서로 cross하는 최소비용의 엣지를 선택하여 연결하고 두 집합을 하나로 합친다.

위 이론의 그림설명

 

 

Kruskal알고리즘

대표적인 최소비용 신장 트리의 알고리즘인 크루스칼 알고리즘의 작동방식.

1. 엣지들을 가중치의 오름차순으로 정렬하고 정점들을 각 컴포넌트로 초기화.
2. 엣지들을 그 순서대로 하나씩 선택하며 이미 선택된 엣지들과 사이클을 형성하지 않으면 연결.
3. 간선이 N-1개다 될 때 까지 반복.

자료구조로 트리를 사용하여 트리의 각 노드가 자식노드가 아닌 부모노드의 주소를 가리키도록한다.

같은 루트를 가진 노드는 하나의 집합(연결)이 된다.

 

크루스칼 알고리즘의 기본코드

 

union의 레벨을 낮추는 weighted-union

find시 부모노드를 변경함으로써 높이를 낮춰줌

 

크루스칼 알고리즘의 시간복잡도는 트리의 높이인 n과 관련된 O(n +m)이다.

약간의 트릭을 주면 O(n+mlog*n)으로 낮출 수 있다.