최소 비용 스패닝 트리 - kruskal 알고리즘

앞써 설명했던 최소 비용 스패닝 트리를 구하는 알고리즘 2번째, 크루스칼 알고리즘이다.

크루스칼 알고리즘 역시 Greedy 알고리즘의 방법으로 구한다. 

크루스칼(Kruskal) 알고리즘

로직은 다음과 같습니다.

1. 비용을 기준으로 간선을 적은 것부터 큰 것 순으로 정렬한다.

2. 적은 비용의 간선부터 하나씩 그린다.(사이클을 만들게 되는 간선은 그리지 않는다)

3. 모든 정점이 선으로 연결될 때까지 2의 과정을 계속한다.

1) 그래프가 주어집니다.

2) 가중치가 낮은 엣지들 순으로 정렬합니다.

3 - 1) 가중치가 낮은 엣지들을 순으로 엣지를 선택해줍니다.

3 - 2) 사이클이 발생하면 사이클 중에 가장 가중치가 높은 선을 선택하지 않고 넘어갑니다.

4) 모든 노드들이 엣지로 연결되면 최소 비용 스패닝 트리가 완성됩니다. 

엣지의 개수는 (노드의 개수 - 1)입니다.