Kruskal 알고리즘이란?
일단 기본적으로 사용되는 상황은 Graph로 구성되는 문제를 해결하기 위한 알고리즘이다. 일단 기본적인 시작을 탐욕적인 방법(Greedy method)을 기반으로 한다.
Greedy method
그래프를 선택함에 있어 이전이나 이후의 경우는 고려하지않고 현재 상태에서 얻을 수 있는 최소의 비용의 케이스를 무조건 선택한다. 아래의 경우를 봐보자.
위의 그래프에서 탐욕적으로 생각한다면 가장 선택해야 할 선은 무엇일까? 비용이 1로 가장 작은 [a, b] 간선을 가장 먼저 선택할 것이다. 그 다음은 무엇일까? 그 이후에는 다음으로 비용이 2로 가장 작은 [b, c]를 선택할 것이다. 이러한 방식으로 계속해서 선택하는 방법을 탐욕적으로 선택한다고 한다.
MST(minimum spanning tree) 최소 비용 신장트리
MST, 최소 비용 신장트리는 그래프 내에서 이미 방문 했던 트리들을 다시 방문하지 않고, 순환하지 않고 모든 노드들을 최소 비용으로 순환할 수 있는 방법을 구하는 문제이다. 이 문제를 풀 경우 우선으로 두어야 할 부분이 두 가지가 있다.
- 그래프가 순환되어서는 안된다.
- 모든 노드를 방문하되 최소 비용으로 모든 노드를 방문해야 한다.
우리는 이러한 두 가지 요건을 반드시 충족하고 문제를 해결해야 한다. 이러한 문제를 해결하기 위한 알고리즘은 다음과 같다.
- 그래프의 순환을 확인 => Union find 알고리즘
- 최소 비용으로 모든 노드를 방문 => Kruskal 알고리즘
Union Find
Kruskal 알고리즘
각 그래프 간의 비용을 오름차순으로 정렬하고 오름차순으로 정렬된 비용중 최소 비용을 계속 선택하되 그래프가 순환되지 않게끔 선택한다.