[알고리즘] 프림(Prim) 알고리즘

개념 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장 해나가는 방법 - 정점 선택을 기반으로 하는 알고리즘이다. - 이전 단계에서 만들어진 신장 트리를 확장하는 방법이다. [과정] 1.

시작 단계에서는 시작 정점만이 MST(최소 비용 신장 트리) 집합에 포함된다. 2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.

(즉, 가장 낮은 가중치를 먼저 선택한다.) 3. 위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복한다.

과정 프림 알고리즘에서는 MST의 후보가 될 간선을 담을 우선순위 큐가 필요 우선순위 큐는 최소의 비용을 가지는 경로가 우선순위를 갖게 한..........