grafo G(N, A) -> grafo (input) albero T(N, A) -> minimo albero di copertura (init: vuoto) PRIM(G) { considera T formato da un nodo e da nessun arco; while(esistono nodi in T adiacenti a un nodo non in T) seleziona l'arco di peso minimo che collega un nodo in T con uno non in T; aggiungi a T sia l'arco selezionato che il nodo che non era in T; restituisci T come il minimo albero di copertura di G; }L'algoritmo deve avere sempre a disposizione l'insieme degli archi6 che collegano un nodo in T con uno non in T. Pertanto, ad un maggiore livello di dettaglio, la procedura dovrà interfacciarsi con una struttura dati per la gestione dell'insieme degli archi. La seguente pseudo-codifica rende esplicito l'utilizzo di tale struttura. Postponiamo invece, al momento, la sua implementazione, tenendo però presente che questa scelta influenza pesantemente le prestazioni dell'algoritmo:
grafo G(N, A) -> grafo (input) albero T(N, A) -> minimo albero di copertura (init: vuoto) insieme I -> insieme di archi che connettono un nodo non in T a un nodo in T (init: vuoto) PRIM(G) { T->N = T->N + un nodo qualsiasi preso da G->N; I = I + tutti gli archi del nodo appena aggiunto; while (I != vuoto) estrai da I l'arco con peso minimo; elimina da I gli (eventuali) archi inutili (*); T->N = T->N + il nodo non appartenente a T fra i due congiunti dall'arco appena estratto; T->A = T->A + l'arco appena estratto; I = I + gli archi che collegano il nodo appena inserito in T con uno non in T; restituisci T come il minimo albero di copertura di G; }Ipotizziamo di avere un tipo di insieme in cui l'inserimento di un nuovo elemento costi e l'estrazione del minimo costi (come per esempio il banale caso di una lista). Il ciclo while verrebbe ripetuto volte ed a ogni iterazione la ricerca del minimo e l'eliminazione degli archi ``inutili''7 (*) costerebbe nel caso pessimo (dovendo scandire tutta la lista). Inoltre l'inserimento degli archi del nodo appena aggiunto nell'albero, costerebbe anch'esso , in quanto verrebbero inseriti al più archi. Il costo totale sarebbe quindi . Quella che noi abbiamo chiamato brutalmente ``eliminazione degli archi inutili'' può essere evitata utilizzando un vettore di dimensione che per ogni nodo non appartente a T tiene conto dell'arco presente in I che lo collega a T. In questo modo a ogni inserimento in I si controlla che non vi sia già nell'insieme un arco che collega T al dato nodo. Nel caso che questo esista viene sostituito dal nuovo arco solo se questo ha peso minore di quello già presente in I e, in tal caso, viene opportunamente aggiornato il vettore degli archi. Questa strategia permette di prevenire la presenza di archi ``inutili'' in tempo costante, mentre prima era necessario un tempo . Nella pratica comunque, la complessità dell'algoritmo resta , dal momento che abbiamo ipotizzato che l'estrazione del minimo costi .
grafo G(N, A) -> grafo (input) albero T(N, A) -> minimo albero di copertura (init: vuoto) vettore FHtracer -> vettore degli archi (init: vuoto) FibHeap FH -> insieme di archi che connettono un nodo non in T a un nodo in T (init: vuoto) PRIM(G) { T->N = T->N + un nodo qualsiasi preso da G->N; FH = FH + tutti gli archi del nodo appena aggiunto; aggiorna FHtracer; while(FH != vuoto) estrai da FH l'arco con peso minimo; T->A = T->A + l'arco appena estratto; T->N = T->N + il nodo non appartenente a T fra i due congiunti dall'arco appena estratto; for each (arc = arco del nodo appena inserito in T) x = nodo congiunto da arc al nodo appena aggiunto a T; if(x non appartiene gia` a T) if(FHtracer[x] == NULL) FH->insert(arc); FHtracer[x] = arc; else FH->decrementaChiave(arc, FHtracer[x]); if(arc->chiave < FHtracer[x]->chiave) FHtracer[x] = arc; restituisci T come il minimo albero di copertura di G; }La complessità dell'algoritmo con l'utilizzo degli heap di Fibonacci si abbassa a
Per renderne più chiaro il funzionamento in seguito è riportata una sequenza di figure che rappresentano i vari passaggi nel calcolo del minimo albero di copertura. In colore nero sono rappresentati gli archi e i nodi che fanno parte dell'albero di copertura, mentre in grigio quelli che non ne fanno parte; tratteggiati sono invece gli archi inseriti nello heap di Fibonacci.