Introduzione

Bentornati alla serie Algoritmi sui grafi! Un albero ricoprente minimo (MST) collega ogni vertice di un grafo pesato usando il peso totale degli archi più basso possibile, senza cicli.

L'algoritmo di Kruskal costruisce l'MST in modo greedy: ordina gli archi dal meno costoso al più costoso e aggiunge ciascuno di essi, purché non crei un ciclo. Il trucco per rilevare rapidamente i cicli è una struttura dati chiamata union-find (nota anche come insieme disgiunto).

Il grafo è non orientato e pesato, ed è rappresentato da n (vertici da 0 a n - 1) e edges, un array piatto di triple [u0, v0, w0, ...] per un arco non orientato u - v di peso w.

Cominciamo!