[알고리즘] 최소 스패닝 트리 - 크루스칼(Kruskal) 알고리즘

스패닝 트리

간선의 수를 최소화 해서 모든 정점을 이용하는 트리이다.

N개의 정점이면 최소 N-1개의 간선으로 이루어져 있고 사이클이 발생하면 안된다.

간선의 수 뿐만 아니라 비용까지 계산해서 최단거리를 구하는 것이 최소 스패닝 트리이다.

 

크루스칼(Kruskal) 알고리즘

지금 이 순간 최선의 답을 선택해 결과를 도출한다. 탐욕적(Greedy) 방법

간선을 간선의 비용이 적은 순서대로 정점개수 - 1 개가 될 때까지 선택한다.

간선을 선택하는 중 사이클이 되면 선택하지 않으며 사이클을 유니온 - 파인드를 이용해 감지한다.

 

https://chanhuiseok.github.io/posts/algo-33/

알고리즘 - 크루스칼 알고리즘(Kruskal Algorithm), 최소 신장 트리(MST)

동작과정에 대해 보기 쉽게 나와있는 링크이다.

유니온 파인드를 이용하는 방법은 간선을 이을 때 도착 정점의 부모를 시작 정점으로 지정하고,

선택할 간선의 시작 정점과 도착 정점이 같은 정점을 가리키고 있을 때 (서로 다른 집합 일 때) 

사이클이라고 인식하고 선택하지 않는다.

 

https://cppking.tistory.com/148

[알고리즘] 상호 배타적 집합 (Disjoint set), 유니온 파인드 (Union find)

유니온 파인드는 정리해 놓은 것 참조.

간선들을 union으로 합칠 때 어떤 간선들이 같은 집합인지만 알면 되기 때문에

트리의 높이는 신경쓰지 않고 정점 중 작은 값을 기준으로 합친다.