신장 트리(spanning tree) G의 간선들로만 구성되고 G의 모든 정점들이 포함된 트리 신장트리는 G의 최소 부분 그래프(간선의 수가 가장 적은 부분 그래프) G'로서 V(G') = V(G)이고 G'는 연결되어 있음 신장트리는 n-1개의 간선 가짐 최소 비용 신장 트리 최저의 비용을 갖는 신장트리 Kruskal, Prim, Sollin 알고리즘 사용 신장 트리의 제한 조건 그래프 내에 있는 간선들만을 사용 정확하게 n-1개의 간선만을 사용 사이클을 생성하는 간선을 사용 금지 Kruskal 알고리즘 한 번에 하니씩 T에 간선을 추가해 가면서 최소비용 신장트리 T를 구축 T에 포함될 간선을 비용의 크기 순으로 선택 이미 T에 포함된 간선들과 함께 사이클을 형성하지 않는 간선만을 T에 추가 G는 연결되..