13.3.2 프림 알고리즘 구현

이전 절에서 설명한 내용을 읽기만 해서는 쉽게 이해할 수 없습니다. 이럴 때는 그림 만한 것이 없지요. 그림으로 자세하게 살펴보겠습니다. 다음 그림부터 보시죠.

▲ 그림 13-30 프림 알고리즘 1

그림 13-30에서 w는 트리 내 정점과 이어진 에지 중 가중치가 가장 작은 에지의 가중치를 의미합니다. 이전 절에서는 이 w를 모아 놓은 w_list를 만들기로 했었지요. from은 가중치가 가장 작은 에지의 트리 내 정점입니다. 그림 위에 표시된 TV는 자라나는 트리의 정점 집합입니다. 다시 말해 구하고자 하는 최소 비용 신장 트리 T의 V(T)입니다. TE는 최소 비용 신장 트리의 에지 집합입니다. 구하고자 하는 최종 목적입니다. 즉, TE는 최소 비용 신장 트리 T의 E(T)를 의미합니다.