이제부터가 핵심입니다. 다음 그림을 잘 보세요.
▲ 그림 13-26 크루스칼 알고리즘 10
그림 13-26을 보면 에지 (0, 3)은 같은 집합에 있습니다. 즉, 이 에지를 추가하면 사이클이 형성됩니다. 그러므로 에지 (0, 3)은 버립니다. 에지 (0, 1), 에지 (1, 4)도 사이클을 형성하므로 버립니다. 이제 에지 (3, 5) 차례입니다. 이 두 정점은 사이클을 형성하지 않습니다.
이제부터가 핵심입니다. 다음 그림을 잘 보세요.
▲ 그림 13-26 크루스칼 알고리즘 10
그림 13-26을 보면 에지 (0, 3)은 같은 집합에 있습니다. 즉, 이 에지를 추가하면 사이클이 형성됩니다. 그러므로 에지 (0, 3)은 버립니다. 에지 (0, 1), 에지 (1, 4)도 사이클을 형성하므로 버립니다. 이제 에지 (3, 5) 차례입니다. 이 두 정점은 사이클을 형성하지 않습니다.