그림 13-27을 보면 사이클을 형성하는 에지들은 모두 버리고 이제 에지 (3, 5) 차례입니다. 3과 5는 서로 다른 집합에 있기 때문에 사이클을 형성하지 않습니다.

▲ 그림 13-27 크루스칼 알고리즘 11

이제 에지를 추가합니다. 그림 13-28에서 에지 (3, 5)를 E=E U {(3, 5)} 연산을 하고 나면 트리가 완성되었습니다. |E|=|V|-1을 만족하기 때문이지요. 이제 알고리즘을 종료합니다.

▲ 그림 13-28 크루스칼 알고리즘 12