[ 신장트리(Spanning Tree) ] 주어진 방향성이 없는 그래프의 서브 그래프(Subgraph)들 중에서 모든 정점을 포함하는 트리 사이클이 존재하지 않습니다. [ MST ] 그래프의 신장 트리 중에서 간선들의 가중치 합이 최소인 신장트리를 MST(최소 비용 신장 트리,Minimum Spanning Tree)라고 합니다. 간선들의 가중치의 합이 최소 V개의 정점 그래프는 V-1개의 간선 사이클 존재 X 총 3가지의 특징을 가지고 있어야 합니다. 최소 비용 신장트리를 찾는 방법은 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 대표적입니다. 두 가지 모두 그리디 방식으로 구현합니다. 최소 비용 신장 트리는 통신 네트워크 구축, 배관 파이프 건설 등에서 사용될 수 있습니다. [ 크루스칼..
