그림 13-10을 보면 가중치가 가장 작은 에지 e=(3, 4)를 선택해서 E=E U {(3, 4)} 연산을 합니다. 그림을 살펴보니 이제 모든 정점이 연결된 트리가 되었습니다. 알고리즘을 종료합니다.

▲ 그림 13-10 탐욕 알고리즘 8

그럼 구한 MST를 확인해 볼까요? 그림 13-11은 탐욕 알고리즘을 이용해서 구한 최소 비용 신장 트리 T를 보여 줍니다.

▲ 그림 13-11 탐욕 알고리즘 9