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

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

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

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

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

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

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

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

▷ 변의 개수 E(간선), 꼭짓점의 개수 V(노드)라고 하면 이 알고리즘은 O (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 (나동빈 님 블로그)