Foresta di supporto di costo minimo: algoritmo di Kruskal

Questa lezione ha come obiettivo l'implementazione dell'algoritmo di Kruskal per trovare la foresta di supporto di costo minimo.

Seguire i seguenti passi implementativi:

1. Leggere, se necessario, lo pseudocodice spiegato nel corso di teoria.
2. Creare una classe Edge che rappresenta un arco pesato con i seguenti campi:
   • public int x: primo nodo dell'arco;
   • public int y: secondo nodo dell'arco;
   • public int c: costo dell'arco;
3. Creare una classe Kruskal con i seguenti campi:
   • public static Edge[] forest: la minima foresta di supporto (rappresentata come un vettore di archi);
   e i seguenti metodi:
   • public static void kruskal(Graph g). Determina la foresta di supporto di costo minimo salvandola nella variabile forest;
   • public static void printForest(). Stampa la foresta contenuta nella variabile forest, il costo, il numero di archi e il numero di componenti connesse della foresta;
   • public static void vizForest(). Salva in formato GraphViz il grafo originario in cui gli archi della minima foresta di supporto sono evidenziati con il colore rosso.

Nota

Per ordinare gli archi, si modifichi un algoritmo ottimale per l'ordinamento (ad esempio HeapSort) affinchč lavori su oggetti di tipo Edge ordinandoli per costo.

Si rappresenti un grafo mediante la classe Graph e si usi la classe DisjointTreeHeuristic per realizzare le operazioni di MakeSet, FindSet e Union.