토픽 30 / 82

최소 스패닝 트리 (MST, Minimum Spanning Tree)

연결된 무방향 가중치 그래프에서 모든 정점을 포함하고 간선 가중치 합이 최소인 트리

목적: 최소 비용 연결, 네트워크 설계, 클러스터링

특징: 트리(V-1개 간선, 사이클 없음), 최소 가중치, 연결

주요 알고리즘: Kruskal(간선 정렬+유니온 파인드), Prim(정점 확장+우선순위 큐)

적용사례: 네트워크 설계(최소 비용 케이블), 클러스터링, 도로 건설, 회로 설계

비교: Kruskal(간선기반/정렬/O(ElogE)/희소그래프) vs Prim(정점기반/우선순위큐/O((V+E)logV)/밀집그래프)

연관: Kruskal, Prim, 유니온 파인드, 그래프