최소 신장 트리 ( MST : Minimal Spanning Tree )

먼저 용어부터 알아보자.

Minimal : 최소

Spanning : (다리를) 놓다. 걸치다. (차 다니는 다리임)

Tree : 나뭇가지, 관계

이 정도로 정리하면 '최소 관계도' 또는 '관계를 만드는 것' 을 의미함을 알 수 있다. 여기서 최소의 의미는 비용적 측면을 의미하는데 비용을 가장 적게 들여서 관계를 만든다는 뜻이다.

자, 이것도 아직 어렵다. 아래 그림을 보면 좀 더 쉽게 정의할 수 있겠다.

[그림 1]

그렇다. 각 꼭지점들을 선으로 연결하는 걸 얘기한다. 단, 가장 적은 비용을 들여서 연결을 해야 하는 것이다. 아래 그림을 보자.

[그림 2]

그림1 은 신장트리를 의미하고 그림2는 최소신장트리를 의미한다. 즉, 선(신장)에 비용이 부여되어 있는데 그 중에서 가장 적은 비용이 발생하는 신장을 선택하는 것이다. 최소 신장 트리 라는 다소 요상한 용어다. 한글화는 블리자드가 짱인데...

최소 신장 트리는 가장 기본적인 조건이 있다. 바로 순환이 되어서는 안된다는 것인데, 트리(Tree)의 개념이 순환이 없는 것을 의미하기 때문이다. 그림1의 (a) 는 트리에 해당하지 않는다. a, b, c 꼭지점이 뱅글뱅글 연결되어 있기 때문이다.

최소 신장 트리(이하 MST)를 구현하는 알고리즘은 2개가 있다.(고 하네요. ;;) 바로 '프림 알고리즘(Prim's algorithm)'과 '크루스칼 알고리즘(Kruskal's algorithm)'이다. 두 알고리즘은 MST를 구하는 가장 잘 알려진 알고리즘이지만 구현 방식에 있어 약간의 차이가 있다. 프림 알고리즘은 꼭지점(정점)을 선택하고 그것과 연결된 가장 적은 비용의 정점을 선택하는 방식이다. 크루스칼 알고리즘은 모든 비용을 순차적으로 나열하여 가장 적은 비용이 드는 간선(신장)들을 선택해 나가는 방식이다. 이 둘의 차이점을 가장 쉽게 설명하고 있는 것은 위키백과 이다. 각각의 내용을 확인하여 차이점을 분명히 알고 넘어가도록 하자.

프림 알고리즘 : http://ko.wikipedia.org/wiki/프림_알고리즘

크루스칼 알고리즘 : http://ko.wikipedia.org/wiki/크루스칼_알고리즘

둘 다 중간에 예제가 있다. 그 예제를 잘 읽어 보면 바로 이해가 되니 반드시 보도록 하자. 단, 프림 알고리즘 설명 중에 빨간색으로 처리한다는 부분이 나오는데 그 부분과 이미지가 맞지 않으니 알아서 보기 바란다.

프림 알고리즘

1. 임의의 정점을 선택

2. 이 정점에서 다른 정점으로 갈수 있는 최소 비용의 정점을 선택하고 이 정점은 집합에서 제외

3. 이 정점에서 다른 정점으로 가는 비용과 기존의 비용과 비교후 더 작은 비용이 있으면 갱신

4. 2-3 번 과정을 n(정점의수)-1 번 반복

크루스칼 알고리즘

1. 간선중 비용이 적은 순으로 소트

2. 가장 적은 비용이 드는 간선부터 차례대로 추가

3. 추가중 사이클이 존재하는 간선은 제외

4. 모든 정점이 연결될 때 까지 2 - 3 과정을 반복

위의 알고리즘을 잘 기억하도록 하자. 전체적인 내용을 이해하면 별도로 외울 필요는 없다. 아주 간단한 알고리즘이기 때문에 개념만 정확히 파악하는 것으로 주안점을 맞추자.

아직 잘 모르겠다고 하시는 분들을 위해서 PPT 자료를 하나 올린다. 파워포인트로 실행해서 반드시 슬라이드 쇼로 봐야한다. 가만히 아래 화살표를 누르면서 보고 있으면 아~ 할 수 있을 것이다. 아주 쉽게 설명이 되어 있기 때문에 기본 개념을 위해 아주 좋은 자료이다.

PPT 자료 보기 : 장형운 님의 자료 [다운받기] (반드시 슬라이드 쇼로 실행시켜 볼 것)

덧붙여, 좋은 자료를 제공해 주신 분들에게 감사 말씀 드린다.

참고 자료 

http://ko.wikipedia.org/wiki/신장_트리

http://ko.wikipedia.org/wiki/프림_알고리즘 

http://ko.wikipedia.org/wiki/크루스칼_알고리즘 

http://celdee.tistory.com/121 

http://i-bada.blogspot.kr/2012/05/mstminimal-spanning-tree.html 

http://blog.daum.net/01050328291/4988640 

http://minxd.tistory.com/13 

http://web.skhu.ac.kr/~mckim1/Lecture/DS/dna/index.html 

http://211.228.163.31/30stair/spanning_tree/spanning_tree.php?pname=spanning_tree 

http://students.ceid.upatras.gr/~papagel/project/prim.htm 

장형운 님의 PPT 자료