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

크루스칼 알고리즘이란?(What is a Kruskal Algorithm?)

---

최소 비용 신장 트리를 구하는 알고리즘중 하나인 크루스칼 알고리즘은 가중치가 부여된 그래프 G = (V, E)가 있을 때 그래프 G를 이루는 G(V)에 대해 가장 가중치가 낮은 엣지부터 각 정점들이 모두 연결될 때까지 간선을 추가한다. 이때 엣지는 사이클이 만들어지지 않는 엣지만 선택해야한다. 그래프가 n개의 정점으로 이루어져 있다면 가중치가 가장 낮은 엣지부터 시작해서 n-1개의 엣지를 선택하여 만들면 된다. 만약 n-1개 미만의 엣지만이 존재한다면 이는 그래프가 애초에 연결 그래프가 아닌 상태이다. 다음은 크루스칼 알고리즘을 이용한 최소 비용 신장 트리 구성 방법이다.

 

 

그래프의 초기 상태 및 각 엣지의 가중치

그래프의 형태와 각 엣지에 대한 가중치를 표로 정리했다. 이를 바탕으로 크루스칼 알고리즘을 사용해보자.

 

 

(4, 6) 엣지 선택

표에서 가장 작은 가중치를 가지는 엣지는은 (4, 6)이다. 엣지를 표시하고 표에 적는다.

 

 

(1, 2) 엣지 선택

표에서 다음으로 작은 가중치를 가지는 엣지는은 (1, 2)이다. 엣지를 표시하고 표에 적는다.

 

 

(0, 2) 엣지 선택

표에서 다음으로 작은 가중치를 가지는 엣지는 (0, 2)이다. 엣지를 표시하고 표에 적는다.

 

 

(5, 6) 엣지 선택

표에서 다음으로 작은 가중치를 가지는 엣지는 (0, 1)이다. 하지만 크루스칼 알고리즘에서 조건은 사이클을 만들지 않는 간선을 택해야 한다. (0, 1)은 정점 0, 1, 2를 사이클 형태로 잇는 엣지이기 때문에 그 다음으로 큰 (5, 6)을 선택한다.

 

 

(2, 6) 엣지 선택

표에서 다음으로 작은 가중치를 가지는 엣지는 (2, 6)이다. 엣지를 표시하고 표에 적는다.

 

 

(0, 3) 엣지 선택

표에서 다음으로 작은 가중치를 가지는 엣지는 (2, 5)이다. 하지만 크루스칼 알고리즘에서 조건은 사이클을 만들지 않는 간선을 택해야 한다. (2, 5)은 정점 2, 5, 6을 사이클 형태로 잇는 엣지이기 때문에 그 다음으로 큰 (0, 3)을 선택한다.

 

 

크루스칼 알고리즘 종료

이 그래프의 정점은 총 7개이고 현재 6개의 엣지를 선택했기 때문에 더 이상 진행할 필요가 없다. 마지막 단계에서 만들어진 신장 트리가 가장 최소의 비용을 가지는 신장 트리이다. 과정에서도 보였지만 크루스칼 알고리즘으로 최소 비용 신장 트리를 만들때 주의해야 할 점은 사이클을 만들지 않아야 한다는 것이다. 사이클을 만들면 그 자체로 최소 비용 신장 트리가 될 수 없다. 다음은 위 과정을 gif로 재생해보았다. 혹시 좀 더 눈에 띄는 과정을 보고 싶다면 봐도 좋다.