Come funziona?

Mantieni un booleano inTree per ogni vertice. Inizia con solo il vertice 0 nell’albero. La frontiera è costituita da tutti gli archi con esattamente un estremo all’interno dell’albero, chiamati archi di attraversamento.

Procedura passo dopo passo:

1. Tra tutti gli archi di attraversamento, scegli quello con il peso minore.
2. Aggiungi all’albero il suo estremo esterno e aggiungi il suo peso al totale.
3. Ripeti finché l’albero non contiene tutti gli n vertici (servono n - 1 archi).

Se a un certo punto non esiste alcun arco di attraversamento ma rimangono vertici all’esterno, il grafo è disconnesso.

Esempio con gli archi [0,1,1, 1,2,2, 2,3,3, 0,3,4]: partendo da 0 scegli 0-1(1), poi 1-2(2), poi 2-3(3); totale 6.