그림 13-17을 보면, 먼저 에지를 가중치에 대해 정렬합니다. 그리고 분리 집합 자료 구조로 집합을 형성합니다. 아직 에지를 하나도 삽입하지 않았기 때문에 모든 노드가 루트가 됩니다.

▲ 그림 13-18 크루스칼 알고리즘 2

분리 집합에서 FIND 연산을 이용하여 에지 (0, 2)의 정점 0과 정점 2가 사이클을 형성하는지 확인합니다. 형성하지 않는군요. 그렇다면 에지를 삽입하고 UNION 연산을 이용하여 두 집합을 하나로 합쳐 줍니다.

▲ 그림 13-19 크루스칼 알고리즘 3