크루스칼 알고리즘(Kruskal Algorithm)

크루스칼 알고리즘

크루스칼 알고리즘은 그래프 내의 모든 정점들을 가장 적은 비용으로 모두 연결하기 위해 사용하는 알고리즘이다. 또 다른 말로는 최소 신장 트리를 구하는 알고리즘이다.

신장 트리란?
그래프 내의 모든 정점을 포함하는 트리로써, 최소의 간선으로 모든 정점이 연결되어 있는 순환성이 없는 부분 그래프이다.

 

알고리즘 원리

그래프에서 간선을 하나씩 추가하며 최소 신장 트리를 만드는 알고리즘이며, 간선을 추가할 때는 그리디 알고리즘을 이용해 비용이 최소인 간선을 선택한다.

 

연결된 정점들의 부모를 기록하며 최소 간선을 선택하며 동작한다.

 

동작 과정

1. 간선의 비용을 기준으로 오름차순 정렬을 해준다.
2. 낮은 비용의 간선순으로 순회하며 최소 신장 트리를 만든다.
   이때 주의할 점은 트리에 순환성이 생기지 않도록 간선을 생성하자.
3. 최소 신장 트리가 될 때까지 2번 과정을 반복한다.

 

예제 문제

프로그래머스

정리글

[JS] 섬 연결하기