[알고리즘]최소신장트리-프림 알고리즘

프림 알고리즘 프림 알고리즘Prim’s Algorithm은 로버트 프림이 만든 알고리즘 입니다. 임의의 하나의 정점을 선택하고 이를 이을수 있는 주변의 정점 중 최소 가중치를 가지는 간선을 추가하고, 간선의 개수가 신장트리 조건에 맞을때 까지 이를 반복합니다. 정리하면 아래와 같습니다. 1. 임의의 정점을 하나 선택해서 최소신장트리에 추가합니다. 2. 현재 최소신장트리와 연결되어있는 정점중, 가장 가중치가 적은 정점을 추가함(단, 해당 정점을 추가했을때 사이 클을 형성하지 않아야 합니다.) 3. “2.” 과정을 신장트리 조건에 만족할때까지 반복합니다. 실제 그래프를 가지고, 프림 알고리즘을 통해 최소신장트리를 구해보겠습니다. 1단계 임의의 점 하나를 최소 신장트리에 추가 합니다. 여기서는 정점1을 추가 했습니다. 2단계 현재 최소신장트리와 인접한 정점 중, 가중치가 제일 적은 정점을 선택 합니다. 후보는 아래와 같습니다. 정점{1,2}를 잇는 간선 정점{1,4}를 잇는 간선 이 중 ...

원문링크 : [알고리즘]최소신장트리-프림 알고리즘