[알고리즘 정리] - Kruskal 알고리즘

 

목차
1. 들어가며
2. 최소 신장 트리(Minimum Spanning Tree)와 크루스칼(Kruskal) 알고리즘
3. 유니온 파인드(Union-Find)

 

 

 

 

들어가며

이번 글에서는 크루스칼(Kruskal) 알고리즘에 대해 정리해보려고 한다. 크루스칼 알고리즘은 최소 신장 트리(Minimum Spanning Tree)를 구하고자 할 때 사용하는 알고리즘이다.

 

 

 

최소 신장 트리(Minimum Spanning Tree)와 크루스칼(Kruskal) 알고리즘

 

 

최소 신장 트리(Minimum Spnning Tree)

 

 

 

 

 

 

 

 

 

 

 

 위의 그림과 같이 방향이 없는 가중치 그래프가 있다고 가정해보자. 여기서 최소 신장 트리란 모든 노드를 잇는 가중치가 최소인 신장 트리를 의미한다.

 

 

 

 

 

 

 

 간단히 말하면 모든 노드들을 최소의 비용으로 방문 할때의 경로를 의미한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 예를 들면 모든 노드를 방문하는 경로는 위와 같이 두 가지의 예를 들 수 있다. 이런 경로들을 신장 트리(Spanning Tree)라고 하며 이중에서 포함된 간선들의 비용이 최소가 되는 신장 트리를 최소 신장 트리라 한다.

 

 

 

 

 

 이러한 신장 트리는 2가지 조건을 만족해야 한다.

 

 

1. 그래프에서 모든 노드를 포함할 것.
2. 정점간 사이클이 존재하지 않을 것.

 

 

 

 

 

 

 

 여기서 정점간 사이클이란 3개 이상의 노드가 서로 연결되서 한쪽 노드에서 출발해서 다시 출발 노드로 돌아올 수 있는 경로가 존재함을 의미한다. 간단히 말하면 3개의 노드가 삼각형 모양으로 연결되었다면 그것은 사이클이 존재한다고 본다.

 

 

 

 

 

 

 

 

 

 

 

 결론적으로 이 그래프의 최소 신장 트리는 위의 그림과 같다. 그렇다면 이런 최소 신장 트리를 구하는 알고리즘이 크루스칼 알고리즘이다.

 

 

 

 

 

1. 그래프의 모든 간선을 비용순으로 정렬한다.
2. 비용이 가장 낮은 간선부터 해당 간선을 포함할 경우 사이클이 생기는 지를 확인한다.
3. 사이클이 생기는 경우 해당 간선을 제외하고, 그렇지 않은 경우 해당 간선을 신장 트리에 포함시킨다.
4. 2, 3의 과정을 끝까지 반복한다.

 

 

 

 

 

 

 

 위의 과정대로 진행하면 최소 신장 트리를 구할 수 있으며 이를 크루스칼(Kruskal) 알고리즘이라고 한다. 모든 간선들 중 비용이 낮은 것 부터 차례대로 확인하므로 매 순간 최선의 선택을 하는 그리디 알고리즘을 일부 활용한다고 볼 수 있다.

 

 

 

 

유니온 파인드(Union-Find)

 

Union-Find 알고리즘

 

 

 

 위에서 언급하였듯이 크루스칼 알고리즘의 두번째 과정에서 해당 간선을 포함하는 경우 사이클이 생기는 지를 확인한다고 하였는데, 이는 Union-Find 알고리즘을 이용한다. Union-Find란 합집합을 찾을때에 사용하는 알고리즘으로 크루스칼 알고리즘에서 두개의 노드가 같은 그래프에 속하는 지를 확인하고자 할 때 사용한다. 만약 두개의 노드가 같은 그래프에 속한다면 사이클이 발생하게 되므로 현재 간선을 포함하지 않는다.