크루스칼 알고리즘의 대표적인 문제로는 섬들 사이에 다리를 연결하는데 거리는 고려하지 않고 비용만을 고려하면서 최소비용으로 모든 섬이 연결되도록하는 문제에서 많이 활용된다.
이 글에서는 크루스칼 알고리즘에 대해 알아보고 코드를 어떻게 구성해야할지 알아보도록 할 것이다.
크루스칼 알고리즘 (Kruskal Algorithm) 이란 그래프 내의 모든 정점들을 가장 적은 비용(cost)으로 연결하기 위해 사용되는 알고리즘이다.
그래프 내의 모든 정점들이 연결되도록하고 사이클이 없는 상황에서 최소 가중치를 가지도록 하는 상황을 만들 때 사용된다. 즉, 최소 신장 트리(MST)를 구할 때 사용되는 알고리즘이다.
신장 트리 (Spanning Tree)
신장 트리란 그래프의 최소 연결 트리를 의미한다.
- 최소 연결이라는 것은 각 정점를 연결하는 간선의 개수가 가장 적은 트리를 의미한다.
- 그래프를 구성하는 많은 노드들 중에서 일부 간선을 선택하여 만들어내는데, 모든 정점들이 연결되어야하며, 정점들 사이에 사이클이 존재해서는 안된다.
- 일부 간선을 선택해 만들어지는 특정상 하나의 그래프에는 여러 개의 신장 트리가 존재할 수 있다.
최소 신장 트리(Minimum Spanning Tree)
최소 신장 트리는 그래프의 간선에 가중치가 존재할 때, 신장 트리 중에서 간선의 가중치 합이 최소가 되는 트리를 의미한다.
크루스칼 알고리즘 (Kruskal Algorithm)
크루스칼 알고리즘은 최소 신장 트리를 구하기 위한 알고리즘이다. 그리디 알고리즘의 일종으로 분류된다.
구현
- 그래프의 가중치를 기준으로 간선들을 오름차순 정렬한다.
- 사이클을 형성하지 않는 경우 해당 간선을 선택한다.
- 선택한 간선을 MST 집합에 포함시킨다.
주의사항
구현의 2번 과정에서 사이클을 형성하게 되면 신장 트리를 만족하지 못하기 때문에 사이클을 형성하지 않도록 주의한다. 사이클 형성 여부를 Union-Find 알고리즘을 적용해서 판단한다.
