최소비용신장트리(minimum spanning tree)-4

prim의 알고리즘

- 임의의 노드를 출발노드로 선택

- 출발 노드를 포함하는 트리를 점점 키워 감

- 매 단계에서 이미 트리에 포함된 노드와 포함되지 않은 노드를 연결하는 에지들 중 가장 가중치가 작은 에지를 선택

가중치가 최소인 에지 찾기

- VA: 이미 트리에 포함된 노드들

- VA에 아직 속하지 않은 각 노드 v에 대해서 다음과 같은 값을 유지

- key(v) : 이미 VA에 속한 노드와 자신을 연결하는 에지들 중 가중치가 최소인 에지(u,v)의 가중치

- ㅠ(v) : 그 에지 (u,v)의 끝점 u

r:출발점

key값이 최소인 노드 찾기

- 최소 우선순위 큐를 사용

: V-VA에 속한 노드들을 저장

: Extract-Min : key값이 최소인 노드를 삭제하고 반환