최소 스패닝 트리(Minimum Spanning Tree, MST)

최소 스패닝 트리(Minimum Spanning Tree, MST)란?

최소 스패닝 트리의 정의는 그래프에서 그래프의 모든 정점을 연결하되, 

사이클이 존재하지 않도록 모든 정점을 간선으로 연결하는 것을 의미한다. 

이때, 간선의 가중치 합을 최소로 하며 연결하여야 한다.

이때 생성되는 최소 스패닝 트리는 무조건 하나의 그래프에서 하나만 생성된다고는 보장하지 못한다.

Generic MST 알고리즘

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

- Generic MST 알고리즘

1. 처음에는 A는 공집합이다.

2. 집합 A에 대해서 안전한 에지를 하나 찾은 후 이것을 A에 더한다.

3. 에지의 개수가 n-1개가 될 때까지 2번을 반복한다.

안전한 에지 찾기

- 그래프의 정점들을 두 개의 집한 S와 V-S로 분할한 것은 컷(cut) (S,V-S)라고 부른다.

- 에지(u,v)에 대해서 u∈S이고 v∈V-S일 때 에지(u,v)는 컷(S,V-S)를 cross한다고 말한다.

- 에지들의 부분집합 A에 속한 어떤 에지도 컷(S,V-S)를 cross하지 않을 때, 컷(S,V-S)는 A를 존중한다(respect)고 말한다.

=> A가 어떤 MST의 부분집합이고, (S,V-S)는 A를 존중하는 컷이라고 하자. 이 컷을 cross하는 에지들 중 가장 가중치가 작은 에지(u,v)는 A에 대해서 안전하다.