Prim

[MST] Prim 알고리즘

• Algorithm
• 2021년 4월 12일

우선순위 큐의 방법을 이용하는 알고리즘으로 vertex를 한개씩 선택하며 최소 비용의 edge를 찾는 방법이다. decrease-key의 개념을 이용하며 decrease-key는 현재 계산된 v노드까지의 거리보다 현재 노드 u부터 v까지의 경로가 더 작다면 값을 갱신해주는 방법을 이용한다. 1. 특징 정점 선택 기반 시작 정점부터 출발하여...