Spanning Tree(신장트리)그래프 내의 모든 정점을 포함하는 트리 모든 정점들이 연결되어 있어야하고, 사이클을 포함해서는 안된다. 그래프의 최소 연결 부분 그래프이다. 최소연결 = 간선의 수가 가장 적다 그래프에 있는 n개의 정점(vertax)을 가지는 그래프의 최소 간선(edge) 수는 (n-1)개이고, (n-1)개의 간선으로 연결되 있으면 필연적으로 트리형태가 되므로 Spanning Tree가 되므로 즉, 그래프에서 일부 간선을 선택해서 만든 트리이다. 신장트리는 깊이 우선 탐색이나 너비 우선 탐색 을 이용하여 사용된 간선만 모으면 만들 수 있다. 하나의 그래프에 많은 신장 트리가 존재할 수 있다. [시작 정점을 바꾸어 가면서 깊이 우선 탐색을 하여 만든 신장 트리 중 일부] 깊이우선 탐색알고..
