처음에는 아직 어떤 정점도 TV에 포함되어 있지 않기 때문에 모두 트리 밖 정점입니다. 그림을 보면 w는 무한대로, from은 None으로 초기화되어 있습니다. 키는 w가 됩니다. 그다음 트리의 시작 정점을 정해야 하는데 임의로 0으로 하겠습니다. 어느 정점을 정해도 상관없습니다. 이제 정점 0의 w를 0으로 하고 최소 힙에 push합니다. 그리고 나머지 정점은 각각의 정점과 그 정점의 w, from을 하나로 묶어 최소 힙에 push합니다. 그럼 최소 힙의 루트 노드에는 정점 0이 있겠지요.

그림을 봅시다.

▲ 그림 13-31 프림 알고리즘 2

그림 13-31을 보면 최소 힙에서 pop하면 w=0인 정점 0이 나오겠군요. 이제 adj[0]을 구하면 adj[0]={1, 2, 3}입니다. 트리 내 정점 집합은 {0}이고 트리 밖 집합 V-TV={1, 2, 3, 4, 5}인데, 이를 컷 cut(TV, V-TV)로 본다면 횡단 에지 중 가중치가 가장 작은 에지 (0, 2)는 최소 비용 신장 트리의 에지가 되겠군요. 에지 (0, 2)를 TE에 삽입하기 전에 adj[0]에 대해 업데이트를 해야 합니다. 트리 내 정점과 트리 밖 정점을 잇는 모든 에지에 대해 기존 w와 from 값을 바꾸어 주면 됩니다.