Foresta di supporto di costo minimo: algoritmo di Prim

Questa lezione ha come obiettivo l'implementazione dell'algoritmo di Prim 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 Prim che usa le classi di sopra con i seguenti campi:
   • public static int[] pi: un vettore tale che pi[i] registra il padre del nodo i;
   • public static int[] cost: un vettore tale che cost[i] registra il costo dell'arco (pi[i], i), oppure 0 se l'arco non esiste;
   e i seguenti metodi:
   • public static void prim(Graph g, int root). Determina la foresta di supporto di costo minimo con prima radice root e la salva nella variabile pi;
   • public static void printForest(). Stampa la foresta contenuta nella variabile pi, 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

Si usi la classe Graph per rappresentare il grafo e la classe MinHeap per implementare la coda con priorità basata sul minimo Q; la priorità di un nodo v della coda corrisponde alla distanza d[v] del nodo dall'albero in costruzione. Dunque:

1. i nodi vengono inizialmente inseriti nella coda con priorià pari alle loro distanze;
2. l'estrazione del minimo corrisponde all'estrazione del nodo con distanza minima;
3. la modifica della distanza per un nodo implica la modifica della priorità di quel nodo nella coda.

Occorre mantenere una corrispondenza biunivoca tra i nodi del grafo e i corrispondenti nodi nella coda. Dato che i nodi del grafo sono interi da 1 a n e uno MinHeap è rappresentato da un vettore con indici interi (da 1 a n o da 0 a n-1), tale corrispondenza biunivoca può essere realizzata da una coppia di vettori di dimensione n il primo dei quali assegna un nodo della coda ad un nodo del grafo e il secondo assegna un sono del grafo ad un nodo della coda.

Il test di appartenenza di un nodo alla coda Q può essere realizzato con un vettore flag di booleani tale che flag[v] è vero se e solo se v appartiene alla coda. Inizialmente tutti i nodi appartengono alla coda e un nodo esce dalla coda quando viene estratto come minimo.