How it works?

각 정점에 대해 불리언(boolean) inTree를 유지합니다. 트리에 정점 0만 포함된 상태로 시작합니다. 프런티어(frontier)는 한쪽 끝점만 트리 내부에 있는 모든 간선을 의미하며, 이를 crossing edge(교차 간선)라고 부릅니다.

단계별 프로세스:

1. 모든 교차 간선 중에서 가중치가 가장 작은 간선을 선택합니다.
2. 해당 간선의 트리 바깥쪽 끝점을 트리에 추가하고 그 가중치를 합계에 더합니다.
3. 트리가 모든 n개의 정점을 포함할 때까지 반복합니다 (이 과정에는 n - 1개의 간선이 필요합니다).

어느 시점에서 교차 간선이 존재하지 않는데 정점이 바깥에 남아 있다면, 그 그래프는 연결되지 않은 상태입니다.

간선 [0,1,1, 1,2,2, 2,3,3, 0,3,4]이 있는 예시: 0에서 시작하여 0-1(1)을 선택하고, 그다음 1-2(2), 그다음 2-3(3)을 선택합니다. 총합은 6입니다.