[알고리즘] MST(2) - 크루스칼 알고리즘 ( Kruskal's Algorithm )

MST의 첫 번째 알고리즘으로 Kruskal's 알고리즘을 살펴보겠습니다.

MST는 주어진 그래프에서 안전 간선을 연결하여 최소한의 비용으로 이루어진 트리를 만드는 것이 목적입니다.

Kruskal's 알고리즘은 안전 간선을 연결할 때 Union - Find 자료구조를 이용합니다.

위의 자료구조를 이해하는 것이 Kruskal's 알고리즘의 핵심이므로 이 내용을 먼저 살펴보겠습니다.

1. Union - Find 

Union - Find 자료구조는 이름 그대로 " 찾고 합치는 과정 " 입니다.

예를 들어, 3개의 트리가 있다고 하겠습니다.

이 트리들은 정점 1, 2, 3, 4, 5, 6, 7, 8이 각각 집합을 이루고 있다가 Union이 진행된 중간 단계입니다.

즉, { 1, 2 }  |  { 3, 4, 5 }  |  { 6, 7, 8 } 이렇게 3개의 집합으로 나뉜 것을 표현했습니다.

각 트리를 집합이라고 표현할 때 대표 값은 그 집합을 대표하는 값입니다.

트리 A의 모든 노드들은 대표 값으로 1을 갖고 있으며, 트리 B의 모든 노드들은 3, 트리 C는 6을 대표 값을 갖습니다.

대표 값이 필요한 이유는 두 정점을 합칠(Union) 때 서로 같은 집합이 아닌지 확인(Find)하기 위함입니다.

예를 들어, 위의 그림에서 1과 2를 합친다고 할 때 두 정점은 대표 값이 1이기 때문에 서로 같은 집합입니다.

그래서 1과 2는 합치는 작업을 하지 않습니다.

사실 1과 2는 이미 Union이 진행된 상태였기 때문에 같은 부모를 갖게 되죠.

바로 뒤에서 살펴보겠지만 서로 다른 대표 값을 갖는 두 집합을 Union하면 대표값을 통일함으로써 Union을 수행합니다.

이 때 두 정점의 대표 값을 확인한 작업이 Find 연산입니다.

다른 예로, 2가 속한 트리A와 5가 속한 트리B는 합칠 수 있을까요?

두 집합의 대표 값은 1과 3으로 다르기 때문에(Find) Union이 가능합니다.

그 결과는 아래 그림과 같습니다.

코드를 구현하는 방식에 따라 두 가지 경우가 됩니다.

트리B가 A에 흡수되면 1, 2, 3, 4, 5 모든 정점의 대표 값은 1이 되고, 트리A가 B에 흡수되면 대표 값은 3이 됩니다.

이런 식으로 두 정점(집합)을 합칠 때 대표 값을 확인하는 작업이 Find 연산이고,

만약 두 집합의 대표 값이 다르면 두 집합을 합치는 작업이 Union 연산입니다.

Union - Find 자료구조를 이해하셨다면 Kruskal's 알고리즘은 매우 쉽습니다.

2. Kruskal's 알고리즘

Kruskal's 알고리즘은 두 개의 트리를 연결하는 모든 간선 중 가장 작은 간선( u , v )를 찾아 MST의 부분집합에 추가합니다.

그래프의 초기 모습입니다.

각 정점안에 있는 숫자는 정점의 이름이고, 색깔은 집합(대표 값)을 의미합니다.

즉 초기값으로 모든 정점에 대해 각 정점이 하나의 집합을 이루도록 합니다.

편의상 색깔을 대표 값으로 표현하겠습니다.

가중치가 가장 작은 간선( 3, 6 )을 선택합니다.

Step1에서 정점 3은 밝은 회색이고, 정점 6은 진한 파란색이므로 두 정점은 다른 집합입니다.

이처럼 Find 연산을 통해 대표 값을 확인하였고,

두 집합이 다른 것이 확인되었으므로 Union을 수행합니다.

두 정점의 색깔을 밝은 회색으로 표현해도 좋고, 진한 파란색으로 표현해도 좋습니다.

가중치가 2인 간선 다음으로 가중치가 작은 간선( 5 , 7 )을 선택합니다.

Step2에서 두 정점 5와 7의 색깔은 다르므로 다른 집합입니다.

따라서 Union을 수행합니다.

이후의 과정은 Step2, Step3와 똑같습니다.

가장 작은 간선을 차례대로 선택하여 양 끝의 정점의 집합이 같은지 다른지 Find를 수행하고, 

Union을 할지 말지 결정합니다.

이후의 설명은 생략하도록 하겠습니다.

Kruskal's 알고리즘은 가장 작은 간선을 차례대로 뽑아 간선을 잇는 두 정점의 집합을 비교하여 Union - Find 연산을 수행합니다.

MST는 최소한의 비용으로 이루어진 트리를 만드는 것이 목적이므로 Kruskal's 알고리즘은 이를 만족하네요 !

이제 이를 어떻게 구현할 수 있을지 수도코드를 살펴보겠습니다.

3. 수도코드

1) line 1

A는 Kruskal's 알고리즘의 결과가 되는 트리의 집합입니다.

어떤 간선이 선택되서 간선을 잇는 두 정점이 다른 집합이면 이 간선을 A에 추가함으로써 Kruskal's 알고리즘의 결과를 생성합니다.

2) line 2 ~ 3

그래프의 모든 정점을 집합으로 만듭니다. ( Make-Set )

Step1에서 모든 정점들의 색깔이 다른 색이였죠?

그렇게 표현한 이유는 모든 각 정점이 하나의 집합을 이루고 있다고 했기 때문입니다.

3) line 4

각 Step을 진행할 때 마다 최소의 가중치를 갖는 간선을 선택했습니다.

MST는 최소의 비용을 갖는 트리여야 하므로 최소의 가중치를 갖는 간선이 먼저 선택되어야 합니다.

따라서 간선들의 가중치를 오름차순으로 정렬시킵니다.

4) line 5 ~ 8

모든 간선에 대해서 Find 연산을 수행합니다.

이 때 간선은 line 4에서 정렬을 시켰으므로 뽑기만 하면 됩니다.

그리고 Find 연산의 결과 두 집합이 다르면 현재의 간선을 집합 A에 추가시키고, 간선을 잇는 두 정점을 Union 합니다.

실제로 Find를 한다는 것은 두 정점의 대표 값을 확인하는 것이며, Union한다는 것은 두 정점의 대표 값을 합치는 것입니다.

코드로 구현할 때 색깔을 칠할 순 없으니까요 !

5) 시간 복잡도

line 5 ~ 8 행의 반복문은 서로 소인 집합 포리스트에 대해 O( E )번의 Find, Union 연산을 수행합니다.

이 때 | V | 번의 make - set 연산까지 합쳐 총 의 시간이 걸립니다.

또한 이므로 

간단하게 시간복잡도를 구하면 위와 같습니다...

자세한 증명은 제 수준을 벗어나네요ㅠ

이상으로 MST의 첫 번째 알고리즘 Kruskal's 알고리즘에 대해 알아보았습니다.

Kruskal's 알고리즘은 간선들의 가중치를 오름차순으로 정렬하고, 간선들을 차례로 선택해서 간선을 잇는 두 정점의 Find 연산을 수행한 뒤, 두 집합이 다르면 Union 연산을 수행하는 알고리즘입니다.