Minimum Cost Spanning Tree

• MST 는 최소비용 신장트리이며 Minimum Cost Spanning Tree 의 약자이다.
• Spanning Tree(신장트리) 는 모든 Vertext(정점)이 간선으로 연결되어있고 Edge 의 개수가 Vertext 개수보다 하나 적은 그래프 를 의미한다.
• 신장트리 (Spanning Tree) 는 모든 정점이 연결되어있는 무방향 연결그래프의 부분 그래프 여야 한다.
  다시 말해, 연결그래프가 주어졌을 때 정점의 개수 - 1(Cycle 이 존재하지 않음) 개의 간선으로 모든 정점을 연결(모든 정점을 포함)할 수 있는 부분 그래프를 의미한다.)
• 연결그래프가 주어졌을 때 생성할 수 있는 신장트리는 유일하지 않다.