Computer Science/Algorithm, Data Structure
-
-
-
-
CS : Algorithm : 최소 비용 신장 트리(MST)Computer Science/Algorithm, Data Structure 2021. 4. 15. 16:51
Spanning Tree (스패닝 트리, 신장 트리) 1. 그래프 내의 모든 정점을 포함하는 트리 2. 최소 연결 = 간선의 수가 가장 적다. n개의 정점을 가지는 그래프의 최소 간선 수는 (n-1)이고, (n-1)개의 간선으로 연결된 그래프는 필연적으로 스패닝 트리가 된다. 3. 하나의 그래프에는 많은 스패닝 트리가 있다. MST (Minimum Spanning Tree) 1. spaniing tree 중, 간선의 가중치의 합이 최소인 트리 2. n개의 정점을 가지는 그래프에 대해서, 반드시 (n-1)개의 간선만 이용해야 한다. 3. 구현 종류 Kruskal MST 알고리즘 Prim MST 알고리즘 Kruskal MST 알고리즘 1. greedy method를 활용하여 모든 정점을 최소의 가중치로 연결..