MST 소개 및 특징
Spanning Tree란, cycle을 갖지 않고 그래프 내의 모든 정점이 연결된 트리를 말한다.
n개의 vertex가 있는 Spanning Tree라면 n-1 개의 edge가 있다.
그렇다면 Minimum Spanning Tree (MST) 가 의미하는 것은
모든 spanning tree에 대해 최소 가중치를 갖는 트리를 말한다.
방금 말한 spanning tree의 특징 외에 추가적으로 MST가 갖는 특징은
위 예시를 통해 확인할 수 있듯이, 그 모양이 유일하지 않다는 것이다.
MST 만들기
MST를 만들기 위해 우리는 edge로 이루어진 집합 A를 설정한다.
우선, A를 비어있는 집합으로 초기화시키고
greedy한 접근을 통해 A를 순회하며 안전한 edge(u, v)를 A에 추가하여 MST를 만든다.
그런데 MST에 안전한 edge라는 것을 어떻게 판단할 수 있을까?
일단, edge를 어떻게 추가해야 할지 단순하게 생각해보면
그래프의 모든 edge들 중 가장 작은 가중치를 갖는 Edge(u, v)를 추가하면 될 것 같다.
그런데 우리는 해당 edge가 안전한지 알 수 없다.
이 문제를 해결하기 위해서 우리는 vertex u를 포함하지만 v는 포함하지 않은 subset S를 설정한다.
어차피 각각의 subset으로 이루어진 그래프는 적어도 서로 한 번씩은 edge로 연결되어야 하기 때문에
각 집합을 잇는 가장 작은 가중치를 선택하면 된다. ( Spanning Tree 정의)
이렇게 각 집합을 분리한 것을 보면 알 수 있듯이
각 트리들을 잇기 전에, 먼저 트리 집합들을 Cut해야 집합을 이을 edge를 선택할 수 있다.
여기에서 Cut은 정점을 서로 겹치지 않은 두 개의 집합 S와 V-S 로 분할하는 것이다. (위 그림의 점선)
MST를 구현하기 위한 key idea는
우리가 임의로 설정한 Cut (S, V-S)는 edge들의 집합 A에 포함된 어떤 edge도 지나지 않는다는 것이다.
만약 edge(u, v)가 Cut을 가로지르려면, 엣지의 한 끝점이 S에 있고 다른 끝점이 V-S에 있어야 한다.
Cut을 가로지르는 모든 edge 중에서 가장 작은 edge를 light edge라고 부른다.
우리는 앞으로 edge(u,v)를 (S, V-S)를 가로지르는 light edge 로 설정한다.
그러면 A에 대해 안전한 edge(u,v)를 얻을 수 있게 된다.
이렇게 G에서 각각의 MST들을 설정하고, 각 MST들을 안전한 edge로 이어서 새로운 하나의 MST를 구성한다.
Kruskal’s Algorithm
- 초기화
각 정점이 자신의 컴포넌트로 시작한다. - 엣지 정렬
두 컴포넌트를 연결하는 라이트 엣지를 찾기 위해 엣지의 가중치를 오름차순으로 정렬한다. - 컴포넌트 합치기
라이트 엣지를 선택해서 두 컴포넌트를 하나로 합친다.
엣지가 사이클을 생성할 수도, 그냥 새로운 컴포넌트를 합칠 수도 있기 때문에 이미 병합된 컴포넌트인지 확인해야 한다.
이렇게 크루스칼 알고리즘은 각 단계에서 최소 가중치 edge를 선택하고
Disjoint-set data structures를 사용하여 사이클 생성을 방지하면서 MST를 구축한다.
과정
Prim’s Algorithm
여러 개의 연결 컴포넌트를 고려해야 하는 크루스칼 알고리즘과는 달리,
프림 알고리즘은 집합 A에 있는 엣지들이 하나의 단일 트리를 형성한다.
1. 초기화
각 정점의 키 값을 무한대로 설정하고, 각 정점의 이전 정점을 NIL로 설정한다.
그리고 임의의 루트 정점 r의 키 값을 0으로 설정한다.
여기에서 Q는 모든 정점을 포함한다.
2. 메인 루프
Q가 공집합 상태가 되기 전까지 반복한다.
Q에서 최소 키 값을 가진 정점 u를 추출하고
Q에 있는, u와 인접한 정점 v의 키값이 w(u,v)보다 크다면
v의 이전 정점을 u로 설정하고, v의 키 값을 w(u,v)로 업데이트 한다.
이렇게 루트 정점 r에서 시작하여, CUT (Va, V - Va) 를 가로지르는 라이트 엣지를 추가하는 과정을 반복하여 MST를 구성한다.
이 과정은 우선순위 큐를 사용하면 효율적으로 구현할 수 있다.
과정
