최소 신장 트리 정리 - MST , Minimum Spanning Tree

이번에는 최소 신장 트리에 대해 공부하고 정리해보고자 한다.
 
MST란?
노드와 간선이 주어지고, 간선간 가중치가 존재했을때, 모든 노드가 간선으로 연결되어 하나의 그래프를 만드는데, 그중 가중치을 가장 낮게 하는 그래프 구조를 말한다.
글로만 보면 무슨 의미인지 잘 이해할 수 없다. 아래 사진을 보자.

 
위처럼 노드,간선, 가중치가 제공되었을때 모든 노드를 연결하는 그래프를 그리는 방법은 아주 다양하게 그릴 수 있다.
위처럼 간선을 연결하여 하나의 그래프를 그릴 수 있다.
하지만, 가중치의 합은 간선의 가중치 값에 따라 서로 다르게 되고, 그래프당 가중치 합은 서로 다르게 된다.
 
이중 가중치 합을 가장 낮게 구성하여 모든 노드를 하나의 그래프에 연결하는것이 바로 MST - 최소신장트리 가 되는것이다.
 
여기서 몇가지 주목해야 하는 점이 있다. 위 사진에서 그래프를 그린것의 간선의 숫자를 새보면, 노드 -1 개의 간선을 가지고 있는 것을 볼 수 있다.
 
또, 위에서 설명할 때 '모든 노드를 하나의 그래프에 연결' 이라는 말을 사용했다. 그럼 여기서 생각나야 할 것이
Union-Find 알고리즘이라 생각한다.
 
Union-Find 알고리즘은 두 노드의 Root를 수정하여 하나의 그래프로 포함시키는 Union과 두 노드가 같은 그래프에 속해있는지 판단하는 Find를 이용할 수 있다.
 
Union-Find의 대표적인 테스크 중 하나는 두 노드간 Cycle이 존재하는지 판단하는 것이였다.
위 최소신장 트리는 두 간선간 Cycle이 발생하면 안되므로, Union-Find 알고리즘을 적극적으로 고려해 볼 수 있다.
 
알고리즘은 아주 간단한다. 간선의 가중치값을 Greedy하게 선택하여 하나씩 그려나가면 최소신장 트리를 만들 수 있다.
 
1. N1 / N2 ( 노드 ) , E ( 간선 ) , V ( 가중치 ) 가 있을때 V를 오름차순으로 정렬한다.
2. N1 과 N2가 하나의 그래프에 속하는지 Find 한다.
2-1. 두 노드의 Root가 같지않으면 V를 result에 더해준다.
3. N1과 N2를 Union 한다.
 
알고리즘은 아주 심플하게 정의할 수 있다.
다음에는 간단한 MST문제를 위 알고리즘으로 한번 풀어보고자 한다.