Prim의 알고리즘

Prim의 알고리즘

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

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

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

왜 MST가 찾아지는가?

-prim의 알고리즘의 임의의 한 단계를 생각해보자.

-A를 현재까지 알고리즘이 선택한 에지의 집합이라고 하고, A를 포함하는 MST가 존재한다고 가정하자.

f를 추가하고 그와 연결된 에지중에서 기존의 key 값보다 작으면 key값 갱신한다.

g의 key값은 2, 파이는 = f가 된다.

key값이 최소인 노드 찾기

-최소 우선순위 큐를 사용

-v-va에 속한 노드들을 저장

-extract-min: key값인 최소인 노드를 삭제하고 반환