(3)최소 비용 신장 트리(MST) Kruskal 알고리즘

Kruskal 알고리즘

1. 에지들을 가중치가 오름차순으로 정렬한다. 

2. 에지들을 그 순서대로 하나씩 선택해간다. 만약 사이클을 이루게 된다면 선택하지 않는다. 

3. n-1개의 에지들이 선택되면 종료된다. 

위의 그림을 보며 신장트리를 만들어보자! (웨이트가 같은 엣지가 있으면 아무거나 선택해도 된다.)

왜 신장트리가 찾아지고 만들어지는 것일까?

임의의 한단계를 생각해보자! A를 현재까지 알고리즘이 선택한 에지의 집합이라고 하고, A를 포함하는 MST가 존재한다고 가정하자! 두개의 cut에 cross되지 않는 엣지들 중 최소를 고르면 당연히 사이클이 만들어지지 않고 안전하게 연결될 것이다. 

그렇고 보니 이론은 정말 간단하다 ! 
정렬 후! 사이클 확인! 최소 가중치의 엣지 더하기 순서를 반복하면 되는 것이였다. 

그럼 구현 법에 대해 알아보자!!

 

사이클 존재 여부 체크

위의 사진과 같이 초기에는 선택된 에지가 없다. 그리고 각각의 연결요소를 하나의 집합으로 표현하면 된다. 
그래서 만약 { g } { h }가 선택이 된다면 합집합을 통해서 { g, h }가 된다. 

최소 가중치의 엣지가 선택하여 위와 같이 합집합이 만들어진다. 

다음의 최소 가중치의 엣지인 c와 i를 추가해준다. 그리고 또 다른 가중치가 2인 엣지를 선택하면 f, g, h가 만들어진다. 

같은 순서로 진행하다가 가중치 4의 간선을 선택하게 되면 아래와 같은 집합을 구성하게 된다. 

 

만약에 위의 사진과 같이 i, g의 6의 간선이 연결되려고 할 때 이미 그 집합에는 i, g가 존재해서 추가되지 못하게 된다. 

1. 최소 가중치의 엣지를 고른다.

2. 서로 다른 집합인지 같은 집합에 속해 있는지 확인 후(사이클이 있는지) 다른 집합이라면 연결 후 집합에 추가 같은 집합이면 다른 가중치의 간선을 선택한다. 

3. 선택 후 모두 연결해준다. 

크루스칼 알고리즘의 수도 코드이다. 

1. 집합 A를 공집합으로 둔다. 
2. 각 정점에 해당하는 집합을 만든다. (초기화 해준다.)
3. 가중치 w에 따라서 정렬해준다. 
4. 정점 u와 정점 v가 속해있는 집합을 찾아서 다르다면
4-1. 둘을 합쳐주고 
4-2. 같다면 무시한다. 

** 팁 ** 

반복의 횟수는 집합의 크기가 n-1까지 하면된다. 수도 코드에서는 A의 크기가 n-1까지 하면된다. 

그럼 이번에는 저 수도코드에 있는 MAKE-SET(v), FIND-SET(v) UNION(u, v)등을 어떻게 구현하면 될지 알아 보겠습니다. 

이전에 집합들을 잘보면 disjoint했다. disjoint는 교집합을 해주면 공집합이 나온다. 즉 모든 집합이 서로 다른 집합이라는 것이다. 

여기서의 집합은 tree를 활용합니다. 꼭 이진 트리이거나 블랙레드 트리일 필요는 없습니다. 별다른 조건은 없습니다. 그리고 상향식 트리로 이루어집니다. 

내려 가면서 연산을 해주는 것이 아니라 올라가면서 연산을 실행해준다. 즉 부모의 레퍼런스만 알고 있으면 됩니다. 
그렇지만 예전에 트리를 만들어가면서 힘들고 고통 받은 기억이 있는데 배보다 배꼽이 더 큰 것이 아닐까 라고 생각할 수 있다. 

그래서 아래와 같이 실질적으로는 배열을 사용한다. 

각 배열은 각각의 부모의 정보가 있으면 된다. 자기가 루트라면 자기를 가리키면 된다. 

findSet(v) v의 루트 노드를 찾는 함수이다.

인자와 인자의 부모가 같은지?에 확인 후 다르다면 재귀를 통해 찾는 방법이다. 자기와 자기의 부모가 같다는 것은 결국 -> 이 노드가 루트인가를 물어보는 것과 같은것이다. 

u, v의 루트를 찾아서 하나의 요소가 부모의 자식으로 들어가면 됩니다. 

x에 y를 자식노드로 넣어버리면 된다. 

시간 복잡도는 

루트 노드를 찾는데 O(h)
찾아서 합치는데 O(1)이다. 

 

총 크루스칼 알고리즘의 총 시간복잡도를 생각해보면 

운이 안좋으면 모든 엣지를 다 봐야할 수 도 있기 때문에 O(m)이고 FindSet은 O(n)이 걸리기 때문에 최악에 상황에서 O(mn)이 될 수 있다. 

시간 복잡도를 줄이기 위한 방법

1. Weight Union 

 만약 위와 같이 작은 트리가 큰 트리의 자식으로 들어가게 되면 트리의 높이가 변하지 않을 수 도 있다. 그렇지만 큰 트리에서 작은 트리로 가면 높이가 변할 수 도 있다. (노드의 개수를 기준으로)

 

코드를 보자!!

위 코드에서 잘못된 점이 있는데 4번과 7번이 바뀌어야한다. 

만약에 u와 v의 루트를 찾은 다음에 x의 크기가 더 크다면 둘이 합쳐지닌 작은 y의 루트는 x가 되는 것이다. 

이와같이 만들어주면 Find-Set의 시간복잡도는 logn이 되도록 바꿀 수 있다. 

2. 이번에는 Find-SET의 함수를 바꿔 보겠습니다. 

왼쪽의 그래프를 오른쪽으로 바꾸는 것입니다. Find를 진행하며 자기가 지나가는 노드들을 잘라서 root노드에 추가해주는 것입니다. g에서 짜르고 f에서짜르고 c에서짜르고 를 반복하며 추가합니다. 여기서 i나 j는 지나가는 노드가 아니라서 신경쓸필요가 없습니다. 

수도코드는 위와 같이 생겼고 사실 이 코드를 실행해주어도 오른쪽과 같은 결과가 나오지 않는다. 왜냐면 직접해보면 안다. 그래도 자기가 따라가고 있는 경로의 높이를 반으로 줄일 수 있다. 

추후에 추가..... 이해 못함 ㅠㅠ 내일 수업시간에 물어보겠습니다. 

처음 보는 수식.....

몇번 로그를 해주어야지 1이 되는지 횟수이다.