최소신장트리 솔루션

[1. 개요]

최소 신장 트리는 아래와 같은 특징이 있다.

최소 신장 트리를 구하기 위해 크루스칼 알고리즘과 프림 알고리즘 두가지가 있으며,

이 중, 한가지 알고리즘의 구현 패턴을 익히도록 한다.

크루스칼 알고리즘 구현 패턴

최소 힙이 필요하다.
weight 가 작은 edge 부터 트리에 추가해본다.
=> 최소힙에서 pop() 한다.
=> 언어 별 최소 힙 사용 패턴을 알아야 한다.
=> https://testkernelv2.tistory.com/476
트리 추가시 Cycle 이 발생하면, 이 edge 는 사용하지 않는다.
=> Cycle 여부 판별을 위해 Union-find 자료구조를 사용하도록 한다.
=> 최적화 된 union-find 구현 패턴을 알아야 한다.
=> https://testkernelv2.tistory.com/482
트리에 추가된 edge 가 N-1 개 이면 중단한다.
=> 트리가 N-1 개의 edge 로 구성된 그래프라는 사실에 주목한다.
현재 까지 트리를 구성한 edge 개수가 N-1 개 이면 중단하지 않고, 최소 힙이 empty 할 때 까지 반복해도 된다.
=> 어차피, edge 개수가 N-1 개 가 된 시점부터, 추가 되는 edge 는 cycle 을 형성할 것이고
=> 이 edge 들은 결코 사용되지 않기 때문이다.

기타 활용 법

[2. 예제]

test_kernelv2