스패닝1 [Algorithm] MST (최소 신장 트리) 프림(Prim) MST(Minimum Spanning Tree 최소 신장 트리) 프림 알고리즘(Prim's algorithm)가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용을 찾는 알고리즘이다. (greedy algorithm 임) 개요프림 알고리즘은 아래의 순서대로 작동한다: 그래프에서 임의의 하나의 정점을 선택한다.선택한 정점과 인접하는 정점들중 최소 비용의 간선이 존재하게되는 정점을 선택한다.1.2 과정을 반복 하여 모든 정점이 선택될까지 한다. 알고리즘이 종료됐을 때 만들어진 트리는 최소 비용 신장트리가 된다. 동작 예제 어떤 점에서 시작하던 관계는 없습니다. 좌측 그래프에서는 임의의 시작점 D를 선택합니다. D지점.. 2017. 7. 7. 이전 1 다음