Computer Science/Algorithm
-
Kruskal 알고리즘이란?Computer Science/Algorithm 2020. 1. 23. 22:11
Kruskal 알고리즘 Kruskal의 알고리즘은 탐욕적인 방법(greedy method)을 이용한다. 탐욕적인 방법은 알고리즘 설계에서 있어서 중요한 기법 중의 하나이다. 탐욕적인 방법이란 선택할 때마다 그 순간 가장 좋았다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 방법이다. 탐욕적인 알고리즘에서 순간의 선택은 그 당시에는 최적이다. 하지만 최적이라고 생각했던 지역적인 해답들을 모아서 최종적인 해답을 만들었다고 해서, 그 해답이 반드시 지역적으로 최적이라는 보장은 없다. 하지만 다행히 Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다. Kruskal의 알고리즘은 최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이클을 포함하지 않는다는 조건에 근거하여, 각 단계..
-
최소 비용 신장트리(MST, Minimum Spanning Tree)란?Computer Science/Algorithm 2020. 1. 23. 19:41
신장트리 신장 트리(spanning tree)란 그래프내의 모든 정점을 포함하는 트리다. 신장 트리는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 또한 사이클을 포함해서는 안된다. 따라서 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다. 하나의 그래프에는 많은 신장 트리가 존재 가능하다. 신장 트리는 깊이 우선이나 너비 우선 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 또한 신장트리는 그래프의 최소 연결 부분 그래프가 된다. 여기서 최소의 의미는 간선의 수가 가장 적다는 의미이다. n개의 정점을 가지는 그래프는 최소한 (n-1)개의 간선을 가져야 하며 (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것은 바로 신장 트리가 된..