크루스칼 알고리즘 (최소스패닝트리,cut property, disjoint set 에 기반하여.)

크루스칼 알고리즘은 최소스패닝 트리를 구하는 알고리즘 중 하나이다.

우선 스패닝 트리에 대해알아보자.

​

스패닝트리 : 그래프의 모든 노드를 포함하는 트리.

-> 즉 한붓그리기 가능하면 그 한붓을 스패닝트리 라고함.

​

한가지 그래프가 있으면 여러개의 스패닝트리가 존재한다.

스패닝트리의 weight = 그 스패닝트리의 가중치합.

스패닝 트리들 중에 weight 가 최소인거 : 최소스패닝 트리.

-> 즉 최소스패닝트리 : 그래프의 모든 노드를 포함하는 트리중에 간선 가중치의 합이 최소인 트리.

​

최소스패닝 트리 구하는 알고리즘중 하나인 크루스칼 알고리즘, 이제좀 감이 잡힌다. 배워보려고 하는데

여기서 우선, 컷정리(cut property) 를 알아야 크루스칼 알고리즘을 배울수있다.

​

컷 프로퍼티란?

컷:트리를 a,b 두 그룹으로 나누는것을 컷이라고함

a를 한가지의컷 이라고 말할 수 있다. 왜냐면 a가 아니면 무조건 b니까 두그룹으로 나눠진것을 의미하기 때문.

암튼, a,b 두 트리를 mst로 이을려면 가중치가 가장 작은 간선을 잇는것이 좋다. 이것이 컷정리다. 초간단하쥬?

​

어쨋건 크루스칼 알고리즘으로 이제 다시 돌아가서, 배워 보자. 크루스칼 알고리즘은 개념은 짱쉽다.

가중치가 작은거부터 연결하다가, 사이클이생기면 연결안한다. 그럼 최소스패닝 트리가 완성된다. 끝임.

​

근데 구현이 어려운이유

1.간선 가중치순으로 정렬하는 것이 어렵다.

2.사이클이 생기냐 안생기냐를 어떻게 체크할거냐.

​

자. 트리가 있는데 하나의 트리 내에서 간선이 하나라도 추가되면 무조건 사이클이 생긴다.

이거 모르겠으면 직접 트리 그려서 해보면됨ㅋㅋ졸신기.

물론 두개의 서로다른 트리 사이에서는 위 내용이 해당 안된다. 졸신기하고 짱이쥬???

​

자. 이걸알고 다시 그래프를 보면 간선을 그을때 이게적용됨.

같은 트리안에 포함된걸 이으면 안됨.

결국 그래프에서 하나의 간선을 이을때 두 노드가 같은 트리에 포함됬는지 아닌지를 판단하면 되는것.

이것이 바로 크루스칼 알고리즘에서 사이클 판단을 어떻게 할건지에 대한 힌트가 된다. 이것은 disjoint set 을 이용하면된다.

​

Disjoint Set 은 두가지 연산을 가진다.

- 첫번째 연산 : 두정점을 하나의 그룹으로 묶어라 라는 연산 : 한가지그룹은 한가지트리로 나타낸다.

- 두번째 연산 : 두정점이 같은 그룹에 속하는가? 를 판별하는 연산