##
크루스칼 알고리즘이란?
크루스칼 알고리즘이란, 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용됩니다.
즉, 그래프에는 정점(vertex)과 간선(edge)가 있는데, 간선에 가중치가 포함되어 있습니다.
그래프 내의 모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구하고 싶을 때 크루스칼 알고리즘을 사용하게 됩니다.
즉, 최소 신장 트리를 구하기 위한 알고리즘입니다.
이를 좀 더 자세히 살펴 보겠습니다. 먼저, 신장 트리에 대한 용어를 알 필요가 있습니다.
신장 트리(Spanning tree)와 최소 신장 트리
신장 트리(Spannging tree)는 다음과 같이 정의합니다.
그래프에서 (1) 모든 정점을 포함하고, (2) 정점 간 서로 연결이 되며 싸이클이 존재하지 않는(tree의 기본 조건) 그래프
예를 들어 아래와 같은 그래프가 있다고 가정해 보겠습니다.
여기서 나올 수 있는 신장 트리들은 여러 가지인데, 아래와 같은 예시가 있을 수 있습니다.
모든 정점이 포함되어 있으면서, 모든 노드는 적어도 하나의 간선으로 연결되어 있습니다.
또한, 연결 관계에서 사이클을 형성하지 않습니다.
따라서 신장 트리는 정점의 갯수가 n개일 때, 간선이 n-1개가 됩니다.
간선 위에 적힌 숫자는 그 간선의 가중치를 말합니다.
왼쪽 그래프는 가중치가 1+5+6+4=16 이고, 오른쪽 그래프는 가중치가 1+2+6+4 = 13 이 됩니다.
이렇게 신장 트리들 중에서 가중치의 합이 최소가 되는 신장 트리를 최소 신장 트리(Minimum Spanning Tree, MST)라고 합니다.
이 그래프에서는 아래와 같은 경우입니다.
위 그래프를 최소 신장 트리(최소 비용 신장 트리)라고 합니다.
크루스칼 알고리즘은 바로 이 최소 신장 트리를 구하기 위한 알고리즘입니다.
[최소 신장 트리를 구하는 문제의 예시]
- 여러 개의 네트워크 지점들이 있는데, 모든 지점들을 유선으로 연결하되 연결선의 총 길이가 최소가 되야 하는 문제
- 도시들을 모두 연결하되, 연결하는 도로의 길이 합이 최소가 되야 하는 문제
- …
크루스칼 알고리즘의 과정
크루스칼 알고리즘은 그리디 알고리즘의 일종입니다.
즉, 그래프 간선들을 가중치의 오름차순으로 정렬해 놓은 뒤, 사이클을 형성하지 않는 선에서 정렬된 순서대로 간선을 선택합니다.
[1] 그래프 간선을 가중치 오름차순 정렬합니다.
[2] a-b 부터 선택합니다.
[3] 그 다음 a-d를 선택합니다.
[4] 그 다음 b-d를 선택하면 a-b-d 사이클이 형성되므로 선택하지 않습니다.
[5] 그 다음 b-c를 선택합니다. 선택된 간선의 갯수가, 정점의 갯수-1 만큼 되면 종료합니다.
사이클 판단하기 - Union & Find 활용
위에서 [4]번 과정에서 싸이클이면 넘어갔었는데, 이것을 코딩할 때는 Union&Find 자료구조를 사용합니다.
- Union-Find 란?
- Disjoint Set (서로소 집합) 을 표현하는 자료구조
- 서로 다른 두 집합을 병합하는 Union 연산, 집합 원소가 어떤 집합에 속해있는지 찾는 Find 연산을 지원하기에 이러한 이름이 붙었음
아래와 같은 그래프가 있습니다.
간선 선택 전, 1번~4번 노드는 초기에 각각 서로소 집합 {1}, {2}, {3}, {4}로 표현될 수 있습니다.
- parent 배열은 각 정점의 root node(부모)를 표현한 배열
- 초기에는 자기 자신이 루트 노드가 되게 초기화 되어 있는 상태 (parent[i] = i)
가중치의 오름차순 정렬한 순서대로 간선 1-2 를 선택합니다.
이 때, 1번과 2번이 같은 집합으로 Union 연산에 의해 합쳐진 것입니다. 그리고 2번의 부모는 1번이 됩니다.
즉, 위에서 1-2 를 연결하면서 Union 연산에 의해 {1}, {2} 집합이 합쳐져서, 서로소 집합 {1, 2}, {3}, {4} 가 된 것입니다.
{1}, {2} 가 서로 합쳐질 수 있는 이유는 각 집합의 루트 노드가 다른 값 (1과 2)이었기 때문입니다.
({1}의 root node는 1, {2}의 root node는 2)
그리고 그 집합 내에서 제일 작은 숫자가 그 집합에서의 루트 노드(root node) 가 되게끔 가정합니다.
즉, 서로 루트 노드(부모)가 다른지 판단하고, 다르다면 Union 연산으로 합칩니다.
그 결과 2번 노드의 부모 노드는 1번이 되었으며, 1번과 2번은 같은 집합이 되었습니다.
다음으로 간선 1-4를 선택합니다.
1과 4를 연결해야 합니다. 1의 루트 노드는 1이고, 4의 루트 노드는 4 이므로 서로 다른 부모를 가집니다.
따라서 Union 연산으로 합칠 수 있으며, 합친 결과 {1, 2, 4} 집합이 되었습니다.
그리고 {1, 2, 4} 집합에서 루트 노드는 1 입니다. 즉, 2번의 부모는 1번이고, 4번의 부모도 1번입니다.
다음으로 간선 2-4를 선택합니다.
2와 4를 연결해야 합니다. 그런데, 2의 루트 노드는 1이고, 4의 루트 노드도 1 입니다.
(parent[2] = 1, parent[4] = 1 –> parent[2] == parent[4])
서로 부모가 같기 때문에 Union 연산을 하지 않습니다. 만약 합친다면 위 그래프처럼 사이클을 형성하게 되기 때문입니다.
즉 사이클을 형성하는지 알아보는 방법은, 각 노드의 부모 노드가 동일한지 아닌지 보는 것으로 알 수 있게 되는 것입니다.
집합 관점에서는, 이미 2와 4가 같은 집합에 속해 있으므로 거기서 또다시 Union 연산을 할 수 없는 것입니다.
크루스칼 알고리즘을 활용한 문제로 삼성 SW 아카데미의 1251번 - 하나로 문제 가 있습니다.
[바로가기]준비중