Kruskal Algorithm

크루스칼 알고리즘(Kruskal algorithm)은 간선을 오름차순으로 정렬한 뒤, 가중치가 낮은 간선을 선택하면서 최소 신장 트리를 생성하는 방식의 그리디 알고리즘이다.

만약 특정 간선을 선택했을 때 사이클이 생성된다면 해당 간선은 선택하지 않고 다음으로 가중치가 낮은 간선을 확인한다. 이 과정을 반복하다가 모든 정점이 연결되면 알고리즘을 종료한다.

크루스칼 알고리즘에서는 가중치의 오름차순으로 간선을 정렬하는 알고리즘과, 사이클의 생성 여부를 판단하는 유니온 파인드(union-find) 알고리즘을 함께 사용한다.

크루스칼 알고리즘의 실행 과정은 아래와 같다.

1. 아래 그림은 최소 신장 트리를 구하기 위한 그래프를 정의한 것으로, 간선의 가중치가 각각 다르다.

   

2. 우선, 아래 그림과 같이 전체에서 가중치가 1로 가장 작으면서 정점 D와 E를 연결하는 간선을 선택한다.

   

3. 이후 가중치가 다음으로 작은, 가중치 3인 간선을 선택한다. 이 간선은 정점 A와 B를 연결한다.

   

4. 이후 가중치가 그 다음으로 작은, 가중치 5인 간선을 선택한다. 이 간선은 정점 B와 D를 연결한다.

   

5. 가중치가 그 다음으로 작은 간선은, 정점 A와 D를 연결하는 가중치 6인 간선이다. 그런데 이 간선을 트리에 포함하면 정점 A, B, D 사이에 사이클이 형성되므로 선택할 수 없다.

   

6. 가중치가 그 다음으로 작은 간선을 찾는다. 정점 C와 F를 연결하는 간선이 가중치 7이므로, 해당 간선을 선택한다

   

   .

7. 가중치가 그 다음으로 작은 간선은, 정점 E와 F를 연결하는 가중치 9인 간선이다. 해당 간선을 선택하면 모든 정점이 연결되므로, 최소 신장 트리가 완성된다!

   

위와 같이, 크루스칼 알고리즘은 정점을 기준으로 트리를 생성하는 프림 알고리즘과 달리 간선을 기준으로 트리를 생성한다. 즉, 흩어져 있는 여러 노드를 가중치가 작은 간선으로 연결해 하나의 최소 신장 트리를 생성하는 것이다.

Book Mark

알고리즘 노드를 그리는 툴은 CS Academy를 활용했다.