예를 들어 adj[0]에 속하는 정점 1을 보면 기존 w 값은 무한대였습니다. 이 값을 이번에 발견한 에지 (0, 1)의 가중치 10과 비교합니다. 당연히 10이 더 작겠지요. 그럼 w 값을 10으로 만들고 이 가중치를 가지는 에지의 트리 내 정점 0을 from으로 합니다. 여기서 그치면 안 되고, 최소 힙에 w 값을 10으로 하는 새로운 요소로 기존 값을 업데이트해야 합니다. 키가 되는 가중치 값이 줄어들었으니까요. 이때 decrease_weight 연산이 필요합니다. adj[0]의 모든 정점을 업데이트한 후 이 알고리즘을 최소 힙이 빌 때까지 계속 반복합니다. 알고리즘이 끝날 때까지 따라가 보겠습니다.

자, 다음 그림부터 봅시다. 그림 13-32를 보면 최소 힙에서 요소를 pop해 오면 w가 가장 작은 정점 2가 나오겠군요. 이때 w=2, from= 0입니다.

▲ 그림 13-32 프림 알고리즘 3