본문으로 바로가기

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


① 크루스칼 알고리즘이란?


최소 비용 신장 트리를 찾는 알고리즘입니다.

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다.

최소 스패닝 트리(MST, Minimum Spanning Tree)를 찾음으로서 간선의 가중치의 합이 최솟값이 되도록 하는 알고리즘이라고도 할 수 있습니다.

   ▶ 스패닝 트리 : 그래프에서 일부 간선을 선택해서 만든 트리.

   ▶ 최소 스패닝 트리 : 스패닝 트리 중에 선택한 간선의 가중치의 합이 최소인 트리.

▷ 변의 개수 E(간선), 꼭짓점의 개수 V(노드)라고 하면 이 알고리즘은 (E log V )의 시간복잡도를 가진다.

   ▶ E(간선): 거리, 비용에 해당되며 선에 해당되는 부분입니다.

   ▶ V(노드): 정점, 도시에 해당되며 동그라미에 해당되는 부분입니다.

유니온 파인드(Union-Find) 개념에 대한 정립이 선행되어야 하므로 꼭 읽어주세요!!! 이 후 구현하는데 사용되게 됩니다.

   ▶ http://brenden.tistory.com/33 


 그림으로 보는 크루스칼 알고리즘 (Kruskal Algorithm)


위의 그래프를 살펴 보았을 때 노드는 6개이고, 간선의 갯수는 9개 입니다.


크루스칼 알고리즘은 다음과 같은 절차로 진행됩니다.

1. STEP(1) : 모든 간선들을 거리(비용,가중치)를 기준으로 오름차순으로 정렬한다.

2. STEP(2) :  정렬된 간선을 순서대로 선택한다.

3. STEP(3) :  선택한 간선의 두 정점이 연결되어 있지 않으면, 해당 두 정점을 연결시킨다.


즉 사이클 테이블을 통해 두 점이 연결되어 있는지 여부를 파악합니다. (Union-Find 알고리즘 이용한다)

▷최소비용 신장 트리에서는 사이클이 발생되면 안되기 때문입니다.


STEP(1)은 위와 같이 모든 간선들을 '거리(비용, 가중치)를 기준으로 먼저 오름차순 정렬'을 수행하였습니다.


STEP(2),(3)을 진행합니다. 위 그림을 보면 가장 가중치가 가장 낮은 3이였던 간선을 선택합니다. 두 노드를 연결해 줍니다.

사이클 테이블에 4의 경우 2로 갱신하게 되고 나머지 경우 모두 1로 갱신하게 됩니다. 손이 가는대로 예시를 만들었더니 조금 안 예쁘게 나왔네요..

위 그림처럼 가장 가중치가 낮은 두 번째 간선을 선택합니다. 사이클 테이블도 갱신해줍니다.

위 그림처럼 가장 가중치가 낮은 세 번째 간선을 선택합니다. 사이클 테이블도 갱신해줍니다.



위 그림처럼 가장 가중치가 낮은 네 번째 간선을 선택하면 안됩니다!!!! 사이클이 생기기 때문에입니다.

그 이유로 가장 가중치가 낮은 다섯 번째 간선을 선택합니다. 사이클 테이블도 갱신해줍니다.


위 그림처럼 가장 가중치가 낮은 여섯 번째 간선을 선택합니다. 6개의 모든 노드가 연결되었기 때문에 이 후에 있는 간선들은 확인하지 않아도 됩니다. 모든 사이클 테이블의 모든 값이 1이 되면서 최소 비용 신장 트리가 만들어진 것을 볼 수 있습니다.


 Kruskal Algorithm 알고리즘 코드



 Kruskal Algorithm 관련 알고리즘 문제


 

(백준 1197) 최소 스패닝 트리 (https://www.acmicpc.net/problem/1197)


해결 코드




참고

  1. https://ko.wikipedia.org/wiki/크러스컬_알고리즘
  2. https://blog.naver.com/ndb796/221230994142 (나동빈 님 블로그)



댓글을 달아 주세요