Minimal Spanning Tree1 최소 신장 트리 ( MST : Minimal Spanning Tree ) 먼저 용어부터 알아보자. Minimal : 최소 Spanning : (다리를) 놓다. 걸치다. (차 다니는 다리임) Tree : 나뭇가지, 관계 이 정도로 정리하면 '최소 관계도' 또는 '관계를 만드는 것' 을 의미함을 알 수 있다. 여기서 최소의 의미는 비용적 측면을 의미하는데 비용을 가장 적게 들여서 관계를 만든다는 뜻이다. 자, 이것도 아직 어렵다. 아래 그림을 보면 좀 더 쉽게 정의할 수 있겠다. [그림 1] 그렇다. 각 꼭지점들을 선으로 연결하는 걸 얘기한다. 단, 가장 적은 비용을 들여서 연결을 해야 하는 것이다. 아래 그림을 보자. [그림 2] 그림1 은 신장트리를 의미하고 그림2는 최소신장트리를 의미한다. 즉, 선(신장)에 비용이 부여되어 있는데 그 중에서 가장 적은 비용이 발생하는 신장을.. 2012. 6. 14. 이전 1 다음
