그림 13-6을 보면 횡단 에지 중 가중치가 가장 작은 에지 e=(2, 3)을 선택해서 E=E U {(2, 3)} 연산을 합니다. 아직 트리가 완성되지 않았습니다.

▲ 그림 13-6 탐욕 알고리즘 4

계속 컷을 나누도록 할까요? 그림 13-7을 보면 E={(0, 2), (2, 3)}을 가로지르지 않는 컷 cut(S, V-S)를 구합니다. 여기서 S={1}이고 V-S={0, 2, 3, 4}입니다.

▲ 그림 13-7 탐욕 알고리즘 5