MinimumSpanningTree
1 Minimum Spanning Tree
- 그래프에는 여러 Spanning Tree가 존재하는데 그중 간선의 합이 최소인 트리를 Minimum Spanning Tree라고 한다
2 Spanning Tree
- 신장 트리란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다
- 사이클이 존재하지 않는 그래프는 트리기 때문에 Spanning Tree라고 부른다
- 트리 자료 구조의 일종이므로 간선의 개수가 노드의 개수보다 하나 작다