최소 신장 트리(MST)

Minimum Spanning Tree : 최소 신장 트리사용된 간선들의 가중치 합이 최소인 트리를 뜻합니다.그래프 내의 모든 정점을 포함하는 트리입니다.최소 신장 트리라고 하며, 그래프의 최소 연결 부분 그래프입니다.간선의 수가 가장 적음n개의 정점을 가지는 그래프는 (n-1)개의 간선으로 연결 됨그래프에서 일부 간선을 선택해서 만드는 트리입니다.최소 신장 트리의 특징DFS, BFS를 사용하여 그래프에서 신장 트리를 탐색할 수 있습니다.하나의 그래프에는 많은 신장 트리가 존재하며, 그 중 가장 작은 가중치의 트리가 최소 신장 트리입니다.사이클이 포함되어서는 안됩니다.이전의 신장 트리와는 상관없이 무조건 최소 간선만을 선택합니다.최소 신장 트리의 사용 사례도로 건설, 전기 회로, 통신, 배관 등 최소의 ..