신장 트리 (Spanning Tree)그래프 내의 모든 정점을 포함하는 트리그래프의 최소 연결 부분 그래프.최소 연결 : 간선의 수가 가장 적다n개의 정점을 가지는 그래프 = 최소 간선의 수는 n-1개 = n-1개의 간선으로 연결 = 트리 형태DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다.탐색 도중에 사용된 간선들을 모음하나의 그래프에는 많은 신장 트리가 존재정점(Vertex) : 모두 포함사이클 : X (트리임)최소 신장 트리(MST)란?가장 간선의 가중치 합이 가장 작은 트리를 의미한다. (최소 비용)MST 사용 사례통신망, 도로망, 유통망에서 길이, 구축 비용, 전송 시간 등을 최소로 구축하려는 경우도로 건설도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제전기 회로단..
