크루스칼(Kruskal) 알고리즘. 이름 좀 멋지네?
널 샅샅이 파헤쳐주마.
개념
그래프의 모든 정점을 최소 비용으로 연결하기 위한 알고리즘!
즉, 그래프에는 정점(Vertex)와 간선(Edge)이 존재하며, 간선에는 가중치(Weight)가 있는데,
모든 정점을 연결했을때 싸이클이 존재하지않고 , 최소 비용의 가중치로 간선을 사용하는 알고리즘이다!
이렇게 모든정점이 싸이클 없이 최소 가중치로 연결된 그래프를 "최소신장트리"라고 부른다.
먼저 신장 트리에 대해 알아보자.
신장 트리
- 그래프에서 (1) 모든 정점을 포함하고, (2) 정점 간 서로 연결이 되며 싸이클이 존재하지 않는 그래프를 뜻한다.
그래프의 신장 트리중에서 가중치 합이 최소가 되는 것이 바로 최소 신장 트리인 것이다.
최소 신장 트리(Minumum Spanning Tree, MST)
아래와 같은 그래프가 있다고 가정해보자.
다음은 위 그래프에서 나올 수 있는 신장 트리의 예시중 일부이다.
신장 트리의 특징은 정점의 갯수가 n개 일때, 간선의 갯수는 n-1개라는 점이다.
따라서 신장 트리 중에서 가중치 합이 가장 작은 최소 신장 트리는 아래와 같다.
알고리즘 과정
크루스칼은 그리디 알고리즘의 일종이다.
따라서 간선을 가중치 기준 오름차순으로 정렬한 뒤, 정렬된 순서대로 간선을 싸이클이 형성되지 않고, 간선의 갯수가 n-1개가 될때까지 선택한다.
-
간선을 가중치 기준 오름차순 정렬한다.
-
a-b 간선을 선택한다.
-
a-d 간선을 선택한다.
-
b-d 간선을 선택해야하지만, 싸이클이 형성되므로 선택하지 않는다.
-
b-c 간선을 선택한다. 간선의 갯수가 n-1개가 되었으므로 완료.
여기서 잠깐, 싸이클은 어떻게 판단할 수 있을까?
이것은 우리가 일전에 학습한 Union-Find를 통해 판단할 수 있다.
disjoint Set과 Union-Find 파헤치기
연결하는 두 정점의 root 노드를 Find 연산을 통해 찾고 root 노드를 비교하여 싸이클 여부를 판단하면 된다.
활용
- 모든 섬을 연결해야할 때, 연결 다리를 설치하는 최소 비용
- 회사의 모든 컴퓨터를 유선으로 서로 연결할때, 연결선의 최소 길이
연습 문제
