Spanning Tree - 신장 트리
노드의 갯수가 N개일때 모든 노드가 연결되어 있고 간선의 갯수가 N-1개인 트리를 Spanning Tree라고 한다. N개의 모든 노드가 연결되어있고 최소 갯수의 간선(N-1)을 가지기 때문에 Spanning Tree는 트리내에 사이클이 존재하지 않는다.
MST (Minimum Spanning Tree) - 최소 신장 트리
MST는 Spanning Tree에서 사용된 간선의 가중치 합이 가장 작은 트리를 의미한다. 모든 노드를 최소한의 간선과 최소한의 비용으로 연결하는것을 말한다.
참고자료
[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io