Complessità temporale e spaziale

Complessità temporale:

• Ordinare i E archi richiede O(E log E); ogni operazione union-find è quasi O(1) con la compressione dei cammini, quindi l'algoritmo classico di Kruskal è O(E log E). La versione con selezione del minimo che costruiamo qui è O(E²), il che va bene per i grafi piccoli.

Complessità spaziale:

• O(V) per l'array dei genitori (più gli archi in input).

Riepilogo:

• Kruskal costruisce un MST aggiungendo a ogni passaggio l'arco senza cicli meno costoso, usando union-find per verificare la presenza di cicli.
• Tutti gli MST hanno lo stesso peso totale, quindi la risposta è unica.