[알고리즘] Minimal Spanning Tree 와 그리디 알고리즘

그리디 알고리즘 해결 방식으로 MST(Minimal Spanning Tree) 를 구해낼 수 있다.

 

Minimal Spanning Tree(최소신장트리) 란?

한국말로하면 최소신장트리 로 그래프를 연결하는 가장 최적의 트리라 생각하면 된다.

모든 정점들을 포함해야하며, 사이클을 포함하면 안된다.(공간을 만들면 안됨)

가장 중요한 것은, 모든 간선의 가중치가 최소가 되는 트리를 Minimal Spanning Tree 라고 한다.

 

안전한 엣지(Safe edge)란?

안전한 엣지란, 우리가 MST를 구하는 과정에서, 현재 선택할 수 있는 엣지를 뜻한다.

예를들어 우리가 MST 를 구하고 있는 중인 어떤 상황일 때, A 엣지를 선택해서 MST를 만드는 경우도 있고 B 엣지를 선택해서 MST를 만들 수 있지만, C 를 선택해서 MST 가 되는 경우가 없다면, A와 B 엣지는 안전한 엣지가 된다.

(당연히 Safe edge는 사이클을 형성하면 안된다.)

 

---

그리디 알고리즘과 MST

우리는 그리디 알고리즘을 이용하여 MST 를 구할 수 있다. 그리디 알고리즘의 아이디어대로 현 상황에서 최적의 엣지만을 선택하는 것이다.

 

루프 불변성 : 모든 반복문에서의 A(현재 그래프) 는 최종 MST 의 부분집합중 하나가 되도록 한다.

우리는 대부분 이 문제를 해결할 때 처음에 엣지가 연결되지 않은 클린한 노드들중에서 하나하나 씩 이어갈 것이다.

그 단계를 거치면서 노드를 하나씩 이어가되 매 차례가 MST 의 부분집합중 하나가 되도록 하는 것이다.

 

결국 현 상황에서 Safe 한 엣지만을 계속 골라 모든 노드가 선택될까지 반복하면 그것이 MST 중 하나가 된다는 결론에 이른다.  

이를 수도코드로 표현하면 이렇다.