크루스칼 알고리즘

https://blog.naver.com/ndb796/221230994142

<크루스칼 알고리즘>

 : 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘

 - 정의) 가장 적은 비용(거리)으로 모든 노드를 연결하기 위한 알고리즘.

 - 쓰임) 여러 개의 도시가 있을 때, 각 도시를 도로를 이용해 최소 비용으로 연결하고자 할 때 적용되는 알고리즘.

 - 핵심idea)

* 간선을 거리가 짧은 순으로 그래프에 포함시키기.

 (1) 간선 정보를 오름차순으로 정렬한 뒤,

 (2) 비용이 적은 간선부터 차례대로 그래프에 포함(연결)시키기.

 (3) 포함시키기 전에, 사이클 테이블 확인하기.(Union-Find 알고리즘 적용.)

 (4) 사이클 형성하는 경우 간선을 포함하지 않음.

 (5) 모든 노드를 검사할때까지 (2)~(4) 과정을 반복

 - 고려할 점)

1) 그래프에서 사이클 체크 어떻게 함?

  : 그래프에 Cycle이 생긴다는 의미는 최소신장트리가 될 수 없다는 의미.

=> Disjoint Set (Union-Find)

크루스칼 알고리즘을 위한 2가지 방식 존재. DFS와 Disjoint Set.

 DFS는 그래프 탐색 기법으로 그래프의 Cycle을 형성하는지 체크.

 Disjoint Set은 집합을 트리로 형성하여 그래프의 Cycle을 형성하는지 체크.

 보통 DFS 방식보다 Disjoint Set이 성능면에서 좋음.

2) 간선의 개수 = 노드의 개수 - 1

3) 시간복잡도 : 정렬에 대부분의 시간이 사용됨.