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

최소 스패닝 트리란?

트리는 N개의 정점이 N-1개의 간선으로 연결되어 있으면서 어느 두 노드를 잡아도 가지 못하는 경로가 존재하지 않습니다.

 

일반적으로 트리를 만들 때, 가중치를 고려하지 않고 트리를 구성합니다.

간선에 가중치가 존재하기 때문에 최소 스패닝 트리가 있는 것입니다.

최소 스패닝 트리는 간선을 N-1개의 간선을 뽑아내서 트리를 구성하면서, 뽑아낸 간선의 총 합이 제일 작아야합니다.

​

최소 스패닝 트리의 주요 포인트

1) 우선 N개의 정점이 트리가 되어야한다.

2) 뽑은 간선의 총합이 제일 작아야한다.

​

구현

1) 트리를 구성하기 위해서는 union-find 알고리즘의 union을 써서 쉽게 구현이 가능합니다.

2) 다음 뽑은 간선의 총합을 제일 작게 해기 위해서는 우선 간선을 오름차순 정렬합니다.

3) 그 다음 간선을 작은 것부터 하나씩 보면서 이 간선으로 이어질 두 노드의 부모를 union-find의 find로 찾습니다.

4) 두 노드의 부모가 같다면 서로 같은 집합이라는 뜻입니다. 그럼 간선을 이어주면 안되고 넘겨야합니다.

5) 반대로 두 노드의 부모가 서로 다르다면 같은 집합이 아니기 때문에 이어줍니다.

6) 이렇게해서 N-1개의 간선이 골라졌으면 종료하면 됩니다.

​

시간복잡도

정렬을 위해 O(N*logN), union-find로 인한 시간과 간선을 하나씩 보는 시간복잡도는 N*logN을 안넘으므로 최종 시간복잡도는 O(N*logN)입니다.