최소 비용 그래프
-
[Algorithm] 최소 신장 트리 (MST, Minimum Spanning Tree)Problem Solving/Algorithm 2020. 3. 8. 19:39
신장 트리 (Spanning Tree) 란? - 그래프 내의 모든 정점을 포함하는 트리 - 사이클이 형성되지 않도록 모든 정점이 연결된 트리 - 최소 연결 부분 그래프로 N개의 정점, N-1개의 간선을 가진다. [예시] 해당 그래프에서 다음과 같은 신장 트리를 구할 수 있다. 최소 신장 트리 (Minimum Spanning Tree) 란? - 주어진 그래프에서 최소한의 비용으로 만든 트리 - 간선 가중치의 합이 최소인 스패닝 트리 - 통신망, 도로망, 유통망 구축 비용 등에 활용 MST 구현 방법 - 크루스칼 알고리즘 (Kruskal's Algorithm) - 프림 알고리즘 (Prim's Algorithm) # 크루스칼 알고리즘 (Kruskal's Algorithm) - 탐욕적 방법을 이용하여 최적의 해..