Graph Algorithm - MST

안녕하세요. 우원입니다.

프림 알고리즘을 공부하면서 최소신장트리의 개념을 언급했습니다.

Minimum Spanning Tree의 앞글자를 따서 흔히들 MST라고 부릅니다.

본격적인 공부에 앞서 생기는 의문을 정리하고 가겠습니다.

첫번째, '신장'이라는 단어는 도대체 어떤 의미로서 사용된 것인가?

-> 우리가 가장 흔히 알고 있는 '신장'의 의미는 콩팥입니다.
하지만 우리는 '신장'이 콩팥의 의미가 아님을 분명히 알고 있습니다!
그렇다면 신장의 다른 의미는 무엇일까요?
바로 신체의 긴 정도를 나타내는 신장(身長)입니다.
신체검사 후 기입했던 검사용지에는 '키'라는 말대신 신장이라고 적혀있는 경우를 많이 보았을 것입니다.
그럼 이제 Span의 의미를 살펴보면서 정의를 내려보도록 하겠습니다.
Span은 '걸치다','뻗어나가다'라는 의미를 가지고 있습니다.
뜻을 유추해보면 신장의 의미는 단순히 신체의 길이뿐만아니라 모든 간선을 걸쳐 연결되어 있는 경로의 길이를 의미한다고 보시면 될것 같습니다.

두번째, 신장트리와 최소신장트리는 같은 것인가?

->신장트리는 가중치를 고려하지 않습니다.
그말은 노드의 개수가 n이라면 n-1개의 간선으로 모든 노드를 연결만 한다면 신장트리가 될 수 있다는 말입니다.
그렇다면 최소신장트리는 무엇일까요?
최소신장트리를 고려할 때는 간선에 가중치가 가해질 때입니다.
비용을 최소화 하는 최적의 신장트리를 최소신장트리라고합니다.

신장 != 腎臟 != 身長 (뻗어나가는 것을 생각하자)
신장트리 != 최소신장트리 (가중치가 주어진 특수한 경우)