(2)최소 비용 신장 트리(MST) Generic MST

최소 신장 트리는 일반적으로 kruskal Alogorithm과 Prim의 알고리즘으로 이루어져있다. 이 두 알고리즘을 알아보기전에 

두 알고리즘은 공통적인 특징을 가지고 있는데 이를 Generic MST라고 한다. 

 

Generic MST에 대해 알아보자!!!

Generic MST

 

1. 처음에는 A = 공집합 으로 둔다.
   
   
2. 집합 A에 대해서 안전한 에지를 하나 찾은 후 이것을 A에 더한다. (MST의 규칙을 어기지 않는 에지를 찾은 후)
3. 에지의 수 n-1이 될 때 까지 2번을 반복한다. 

안전한 엣지 찾기
그럼 위의 알고리즘을 완성하기 위해 안전한 엣지를 찾는 방법에 대해 알아보자

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

2. 에지 (u, v)에 대해서 u가 s에 속하고 v가 v-s에 속할 때 에지 (u, v)는 컷 (S, V-S)를 크로스한다고 말한다. 

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

나도 처음에 보고 무슨말이지 하고 생각했는데 아래의 사진을 보고 좀 더 이해가 됐다.

위의 사진을 보면 크로스의 뜻과 존중한다와 cut의 의미를 잘알 수 있을 것이다. 

말이 좀 길어 졌는데 결국 안전한 엣지란 무엇이라면 

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

사진으로 예를 들면 5라는 엣지를 갖고 있는 라인을 선택하면 안전하다고 표현할 수 있다. 안전하다는 것은 최소 신장트리에 새로운 에지를 통해 연결을 해도 최소 신장트리의 조건을 깨지 않으면서 연결이되는 것을 뜻한다.