알고리즘> 그래프> 최소신장트리> 크루스칼 알고리즘

크루스칼 알고리즘

모든 간선을 리스트에 최소값부터 나열한다.

하나씩 뽑으면서 사이클이 생기면 빼고 사이클이 안 생기면 연결한다.

 

사이클 확인하는 법

Union find 알고리즘을 사용

각 노드의 루트 노드를 불러와서 같으면 사이클이 생긴다는 의미

다르면 연결한다.

합치는 방법

막무가내로 합치다가 최악의 상황이 다음처럼 될 수 있음..

루트 노드 찾는데 N개의 노드 모두를 순례할 수 있음..

효율적으로 하기위해 다음과 같은 방법이 사용된다.

 

Union by rank 기법

각 트리 높이를 기억하고 union 시 두 트리 높이가 다르면 작은 트리를 큰 트리에 붙인다. 

높이가 다를 경우

높이가 같을 경우

링크드리스트처럼 길어지게 만드는 게 아니라 차곡차곡 쌓이게 하는 과정이다.

따라서 N개 계산되는 것을 막고 log(N)까지 줄일 수 있다. 

 

Path compression 방법

루트 노드로 다이렉트로 붙인다.

 

 

Union by rank와 Path compression을 사용하면 시간 복잡도가 상수로 줄어든다. 

Union Find의 시간 복잡도 증명 (secmem.org)

Union Find의 시간 복잡도 증명

---

코드예시