mst

[Algorithm] MST(최소 신장 트리)와 크루스칼(Kruskal), 프림(Prim) 알고리즘 정리

MST(최소 신장 트리, Minimum Spanning Tree)란?MST(최소 신장 트리, Minimum Spanning Tree)는 가중치 그래프에서 모든 정점을 연결하는 간선들의 부분 집합 중에서 최소 비용을 가지는 트리이다.즉, 모든 정점을 연결하면서 간선의 가중치 합이 최소가 되는 부분 그래프를 의미한다.MST의 특징모든 정점이 연결되어 있어야 함 (Connected Graph)사이클(Cycle)이 포함되지 않음 (Tree)(N-1)개의 간선으로 구성됨 (N개의 정점을 가지는 그래프라면 MST의 간선 수는 N-1)가중치 합이 최소여야 함MST의 활용통신 네트워크 구축 (최소 비용으로 도시 연결)전력망 설계 (최소 비용으로 전선 연결)도로 네트워크 최적화이미지 처리, 군집화(Clustering) ..