프림 알고리즘
-
[알고리즘] 최소 신장 트리 개념P.study 2020. 6. 17. 03:08
책을 보면서 그리디 알고리즘으로 최적해가 보장되는 예로 최소 신장 트리가 있었다! 당연히 기억 안나니까 한번 공부해 볼까?!! 최소 신장 트리 " 간선들이 가중치를 갖는 그래프에서 가중치의 합이 가장 작은 트리를 말한다. " 최소 신장 트리를 찾는 알고리즘을 공부해보려 한다. 1. 프림 알고리즘 : 시작점을 기준으로 모든 정점을 포함할 때까지 인접한 정점에서 가중치가 가장 작은 간선을 선택하여 하나씩 확장해 나간다. [순서] 1. Start 에서 바라보면 8,9,11 중에서 가장 가중치가 낮은 간선을 택한다. 2. 연결되어 있는 간선들 중에 가중치가 가장 낮은 9를 선택한다. 3. 연결된 간선(1,10,11,12,13) 중 가장 낮은 5를 선택한다. 4. 연결된 간선(11,12,13) 중 가장 낮은 11..