[알고리즘][Graph] 최소 비용 신장 트리 #2 크루스칼(Kruskal) 알고리즘 개념 및 수행과정

학습목표
1. Kruskal 알고리즘의 개념에 대해서 학습
2. Kruskal 알고리즘의 수행과정에 대해서 학습
3. 왜 Kruskal 알고리즘을 수행하면 최소비용 신장트리가 탐색되는지에 대해서 학습

 

1. 크루스칼(Kruskal) 알고리즘이란 무엇인가?

크루스칼 알고리즘이란 무방향 가중치 그래프가 존재할때 해당 그래프에서 최소비용 신장트리를 탐색하는 알고리즘입니다. 이때 최소비용 신장트리란 그래프 내의 모든 정점을 포함하고 사이클(cycle)이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 트리를 의미합니다. 이러한 최소비용 신장 트리를 탐색하는 알고리즘이 크루스칼 알고리즘입니다.

 

2. 크루스칼(Kruskal) 알고리즘의 수행과정

크루스칼 알고리즘의 수행과정은 다음과 같습니다.

1. 에지들을 가중치의 오름차순으로 정렬
2. 에지들을 그 순서(오름차순)대로 하나씩 선택함. 단, 이미 선택된 에지들과 사이클(cycle)을 형성하면 선택되지 않음
3. n-1개의 에지가 선택되면 종료함 (부분집합 A의 개수=n-1)

 

3. 왜 크루스칼 알고리즘을 사용하면 최소비용 신장트리(Mininum Spanning Tree, MST)가 탐색되는가?

아래의 그림은 크루스칼 알고리즘의 임의의 한 단계입니다. 부분집합 A를 현재까지 알고리즘이 선택한 에지의 집합이라 하고, A를 포함하는 MST가 존재한다고 가정합니다.

위 그림에 대한 집합의 정보는 다음과 같습니다. 이렇게 분할된 집합 S와 집합 V-S를 Cut (S,V-S)로 표현합니다.

• V = {a,b,c,d,e,f,g,h,i}
• S = {d,e,f}
• V-S = {a,b,c,g,h,i}

 

위 그림에서 최소비용 신장트리를 탐색하기 위한 부분집합 A의 원소들은 다음과 같습니다. 에지간의 순서는 상관없습니다.

• A = {(a,b), (b,c), (a,h), (h,g), (d,e), (e,f)}

 

위 그림에서 집합 S와 집합 V-S간의 원소와 연결된 에지들은 다음과 같습니다. 이러한 에지들을 Cross한다고 합니다.

• Cross = {(g,f), (c,f), (c,d)}

Cross 집합의 에지들 중에서 가중치가 가장 작은 에지는 파란색 선의 에지인 (g,f)라고 가정합니다.

 

위와같은 상황에서 크루스칼 알고리즘은 Cross하는 에지들 중 가장 작은 가중치를 가지는 에지를 선택하여 최소비용 신장 트리를 탐색합니다. 

 

크루스칼 알고리즘이 안전한 에지를 선택할 수 있는 이유는 부분집합 A는 공집합으로 시작하기 때문에 크루스칼 알고리즘으로 선택한 에지는 A에게 안전한 에지이기 때문이다. 위의 상황까지는 알고리즘이 잘 선택해왔고 Cross하는 에지들을 선택하는 순간에 크루스칼 알고리즘은 Cross하는 에지들 중 가장 작은 에지를 선택하여 싸이클을 생성하지 않도록 합니다. 알고리즘이 Cross하는 에지들 중 가장 작은 에지를 선택하지 않게 된다면 싸이클이 발생되어 문제가 됩니다.  

 

정리하면 Cut (S,V-S)가 존재할때 두 집합이 Cross하는 에지들은 Respect하는 동안은 싸이클이 형성되지 않는다. 그러나 크루스칼 알고리즘이 Cross하는 에지들을 선택하는 순간에는 싸이클을 형성하지 않고 가중치가 최소인 에지를 선택해야 한다. 이러한 에지를 MST에 안전한 에지라고 합니다. 이와 같은 과정을 크루스칼 알고리즘은 모든 에지들에 수행하면 최선의 최소비용 신장트리를 탐색합니다.

 

References

source code : https://github.com/yonghwankim-dev/inflearn_algorithm
[인프런] 영리한 프로그래밍을 위한 알고리즘 강좌