[알고리즘] MST / Disjoint set / 크루스칼 알고리즘

MST 알고리즘

크루스칼과 프림 알고리즘은 MST 를 구하는 알고리즘 의 2종류이며, 그리디 알고리즘을 이용한다.
MST 와 그리디 알고리즘의 정보는 :
https://programming119.tistory.com/78

 

크루스칼 알고리즘

 

나무와 숲

 -> 크루스칼 알고리즘은 각각의 노드를 나무로 생각하고, 모든 노드의 집합을 숲 이라고 생각한다.
 
숲에 나무들이 많다. 이 숲은 마법의 숲이라 나무끼리 손을 잡는다. 나무들끼리는 손을 잡을 수 있을 수도 있고, 나무들끼리 손을 잡으려면 마력을 소비하고 각각 나무들끼리 몇의 마력이 드는지는 정해져 있다.
예시) A 와 B 나무는 손을 잡을 때 3의 마력이 들고 , A와 C는 손을 잡을 때 10의 마력이 들고, B와 C는 손을 못 잡는다.
 
나무 : 노드
숲 : 노드의 집합
나무끼리 손을 잡는 것 : 엣지
손을 잡는데 드는 마력 : 엣지의 가중치
라고 생각하면 된다.
 
우리는 나무들끼리 손을 잡게해서 최종적으로 소외된 나무가 없는 숲을 만들 것이다.
대신 조건이 있는데, 나무들끼리 손을 잡아서 원이 만들어지면 안되며 (사이클), 마력이 최대한 적게 들도록 해야한다!
 
최종 방식은 이렇게 결정된다.
=> 숲을 이루는 나무들중 마력이 가장 조금 들고, 원이 만들어지지 않게 나무들끼리 손을 잡게 반복시키며, 숲에 모든 나무들이 소외되지 않았을 때 이 행동을 그만한다!
 
이를 다시 그래프적인 측면으로 생각하면
=> 가장 낮은 모든 엣지를 오름차순 정렬한 후, 트리형태를 깨지 않는 가장 작은 엣지부터 선택해서 모든 노드가 선택될때까지 반복한다.

---

Disjoint-Set Forest

크루스칼 알고리즘은 Disjoint-set forest 자료구조를 이용한다.
이는 노드끼리 트리를 형성했는지 확인할 때 유용하다!  (여기서의 트리는 나무가 아님, 자료구조로서의 트리임)
 
Make-Set : 노드 를 받아 본인 자신을 가리키게끔 해서, 1개짜리 트리를 만든다.
Find-Set : 루트노드를 찾는다. 트리구조를 깨는지 확인하는 작업 / Comprehension 작업
Union : 트리구조를 깨지않을 때, 두개 노드를 연결해주는 작업
Link : 두 트리를 연결해준다.
Rank = 트리의 크기를 표현, depth이지만 트리구조가 변하면서 depth 를 나타내지 않을 수도 있다.

출처 : 고려대학교 정순영 교수님 알고리즘 강의 

---

최종 알고리즘 수도코드

출처 : 고려대학교 정순영 교수님 알고리즘 강의