신장 트리(Spanning Tree) 그래프 내의 모든 정점을 포함하는 트리 모든 정점들이 연결되어 있고 사이클을 포함하면 안된다. 그래프의 최소(간선의 수가 가장 작은) 연결 부분 그래프 n개의 가지는 그래프는 최소한 (n-1)개의 간선을 가진다. 간선에 비용을 붙여 링크의 구축 비용까지를 고려해 최소 비용의 신장 트리를 선택해야함 통신 네트워크 구축에 많이 사용 최소 비용 신장 트리(MST) 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결 신장 트리 중에서 사용된 간선들이 가중치 합이 최소인 신장 트리 Kruskal, Prim 알고리즘이 대표적 반드시 n-1 개의 간선만 사용하고, 사이클이 포함되어서는 안된다. Kruskal 의 MST 알고리즘 탐욕적인 방법(greedy metho..