How it works?

Mantenha um booleano inTree para cada vértice. Comece com apenas o vértice 0 na árvore. A fronteira é cada aresta com exatamente uma extremidade dentro da árvore, chamada de crossing edge (aresta de cruzamento).

Processo Passo a Passo:

1. Entre todas as arestas de cruzamento, escolha aquela com o menor peso.
2. Adicione sua extremidade externa à árvore e adicione seu peso ao total.
3. Repita até que a árvore contenha todos os n vértices (isso leva n - 1 arestas).

Se em algum momento não existir nenhuma aresta de cruzamento, mas ainda restarem vértices fora, o grafo está desconectado.

Exemplo com as arestas [0,1,1, 1,2,2, 2,3,3, 0,3,4]: a partir de 0 pegue 0-1(1), depois 1-2(2), depois 2-3(3); total 6.