신장 트리(Spanning Tree)신장 트리(Spanning Tree)란 그래프 내의 모든 정점을 연결하는 트리입니다. 신장 트리의 속성- N개의 정점이 있는 그래프의 경우 해당 그래프에 대한 신장 트리의 간선 개수는 N-1개입니다.- 연결이 끊어진 그래프에는 신장 트리가 없습니다.- 신장 트리에는 순환이 없습니다. 하나의 정점에서 출발하여 해당 정점으로 다시 이어지는 간선이 존재한다면 신장 트리가 아닙니다. 최소 신장 트리(MST, Minimum Spanning Tree)그래프 내에 존재하는 Spanning Tree 중 사용 간선들의 가중치 합이 최소가 되는 트리를 MST(Minimum Spanning Tree), 최소 신장 트리라고 합니다. 최소 신장 트리의 속성- N개로 이루어진 그래프라면 반드시..
