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

Kruskal Algorithm :

그래프 내의 모든 노드들을 가장 적은 비용으로 연결하기 위해 사용하는 알고리즘. / greedy algorithm으로 분류됨. / 최소 신장 트리를 만들기 위한 알고리즘(신장 트리 = spanning tree, 하나의 그래프가 있을때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미, 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 함 / 최소 신장 트리 = minimum spanning tree, 신장 트리 중에서도 최소한의 비용으로 만들 수 있는 최소 신장트리를 찾는 알고리즘). / 그래프에는 vertex(정점)와 edge(간선)이 있는데, edge에 가중치가 포함되어 있음. / 여러개의 vertex가 있을 때, 각 vertex를 edge를 이용해 연결하려고 하는 경우 비용을 최소한으로 하기 위해서 사용하는 알고리즘. 

 

모든 정점이 포함되어 있으면서, 모든 노드는 적어도 하나의 간선으로 연결되어 있고 연결관계에서 사이클을 형성하지 않아야함. 따라서 신장트리는 정점의 개수가 n개일 때, 간선은 n-1개가 됨. 간선 위의 적힌 숫자는 그 간선의 가중치이고 가중치의 합이 최소가 되는 신장트리가 최소 신장 트리. 크루스칼 알고리즘은 바로 이 최소신장 트리를 구하기 위한 알고리즘.

 

최소 신장트리의 예시 - 여러 네트워크 지점이 있을때, 모든 지점을 선으로 연결하지만 연결선의 총 길이가 최소가 되어야 하는 경우. / 도시들을 모두 연결할 때, 도시를 연결하는 도로들의 길이 합이 최소가 되어야 하는 경우.

 

크루스칼 알고리즘의 동작 과정 :

① 간선 데이터를 비용에 따라 오름차순으로 정렬 -> ② 간선을 하나씩 확인하여 현재의 간선이 사이클을 발생시키는지 확인. (사이클이 발생하지 않는 경우 최소 신장 트리에 포함. / 사이클 발생하는 경우 최소 신장 트리에 포함 x) -> ③ 모든 간선들에 ②과정을 반복.

 

a-b	b-c	c-d	a-d	b-d
1	3	4	2	2

위 그래프와 같이 연결돼 있는 그래프가 있을 때,

1. 그래프 간선을 가중치 오름차순으로 정렬함.

a-b	a-d	b-d	b-c	c-d
1	2	2	3	4

2. a-b부터 선택

3. 그 다음 a-d를 선택

4. b-d를 선택하면 a-b-d가 사이클을 형성하므로 선택 x

- 사이클 판단은 Union Find 자료구조를 사용. ( Disjoint set(서로소 집합)을 표현하는 자료구조 )

5. b-c 선택. 선택된 간선의 개수가 정점의 개수 -1 만큼되면 종료.

 

크루스칼 알고리즘의 핵심 개념 -> 간선을 거리가 짧은 순서대로 그래프에 포함시키기

 

크루스칼 알고리즘의 시간 복잡도 = 정렬 알고리즘과 동일 (정렬 알고리즘 + Union Find 알고리즘) 

-> O(NlogN)

간선의 개수가 N개 일 때, O(NlogN), 시간이 가장 오래 걸리는 부분 = 간선을 정렬하는 작업. N개의 데이터를 정렬했을때의 시간 복잡도와 같음. 크루스칼 내부에서 사용되는 서로소 집합 알고리즘의 시간 복잡도는 정렬 알고리즘의 시간 복잡도보다 작으므로 무시함.