Algoritmo di Prim

L'algoritmo di Prim, così chiamato dal nome del suo ideatore Robert C. Prim, è un algoritmo utilizzato in teoria dei grafi, informatica e ricerca operativa per determinare gli alberi di connessione minimi (d'ora in poi MST, dall'inglese Minimum Spanning Tree) di un grafo.

Questo algoritmo fa parte della categoria cosiddetta degli algoritmi golosi o greedy.

Come l'algoritmo di Kruskal anche quello di Prim deriva da un più generico algoritmo che semplicemente dato un grafo G = (V,E) con V ed E rispettivamente l'insieme dei vertici e degli archi di G, cerca un arco leggero nel grafo e lo aggiunge all'MST G_A = (V,A) inizialmente vuoto.

Questi algoritmi vengono spesso utilizzati per determinare se un grafo è connesso, oppure qual è il numero di componenti connesse, dato che ogni albero di connessione rappresenta una componente connessa.

Per la descrizione dell'algoritmo si assume il grafo sia rappresentato utilizzando una struttura dati detta lista delle adiacenze che è solitamente realizzata con un array cui ogni posizione corrisponde un vertice. Ogni elemento dell'array punta ad una generica lista concatenata che conterrà tutti i vertici adiacenti al vertice considerato. Inoltre si assume che ogni vertice v abbia i campi dato chiave[v] e π[v], rispettivamente il valore associato al vertice e il puntatore al padre di quest'ultimo all'interno dell'MST.

Fasi dell'algoritmo

1. Inizialmente si pongono tutti i campi chiave[v] a +∞ e tutti i campi π[v] a NIL.
2. Si prende un vertice qualsiasi come radice dell'albero e si pone la sua chiave a 0.
3. Si inseriscono tutti i vertici rimasti in una struttura dati appropriata (tipicamente una coda di priorità) e li si estrae in ordine crescente.
4. Si scorre quindi la lista delle adiacenze del vertice estratto (u) considerando solo i vertici (v) ancora all'interno della struttura ausiliaria.
5. Per ognuno di essi tale che la sua distanza da u sia la minore tra tutti quelli considerati, si pone π[v] uguale ad u inserendo di fatto v nell'MST.
6. Si conclude il ciclo aggiornando il campo chiave[v] con il valore della distanza tra u e v.

L'utilizzo di una struttura dati ausiliaria è auspicabile per evitare di dover controllare continuamente se il vertice considerato in uno dei passi dell'algoritmo sia già stato visto precedentemente.

In altre parole, dato un grafo G=(V,E) (V è l'insieme dei vertici o nodi, E è l'insieme degli archi) ed un albero di soluzione S in cui porremo i nodi raggiunti nei vari passi dell'algoritmo procediamo nel seguente modo: pongo in S un nodo di partenza (arbitrario) dal quale poi sceglierò l'arco incidente di peso minimo non collegato a nodi facenti parte dell'albero di soluzione S. Effettuata la scelta del ramo dal passo precedente includerò in S il vertice collegato al vertice di partenza dal ramo appena scelto. Ad ogni vertice che includo in S anche i rami incidenti di quel vertice si aggiungeranno ai rami tra cui sceglierò quello meno costoso che collega ad un vertice non appartenente ad S. L'algoritmo termina quando la cardinalità (numerosità) di S è pari a quella di G (ciò vale solo se il grafo è connesso).

Analisi della complessità

La complessità dell'algoritmo di Prim dipende dall'implementazione della struttura dati ausiliaria utilizzata per contenere i nodi al passo (3). Se implementata con una coda di priorità e assumendo di complessità costante il test di presenza o meno nella coda il tempo totale di esecuzione dell'algoritmo è di $O(V\cdot\log{V} + E\cdot\log{V})$ dove $V\cdot\log{V}$ è il tempo necessario per le operazioni di estrazione dalla coda ed $E\cdot\log{V}$ è il tempo necessario per scorrere le liste delle adiacenze e compiere l'assegnazione di cui al passo (6).

Quindi il tempo totale di esecuzione dell'algoritmo di Prim è $O(E\cdot\log{V})$.

Bibliografia

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, Seconda Edizione. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Sezione 23.2: The algorithms of Kruskal and Prim, pp.567–574. Edizione Italiana da pag. 480 a pag. 490.
• Robert E. Tarjan, Data structures and network algorithms, Philadelphia, Society for Industrial and Applied Mathematics, 1983. ISBN 978-0898711875

Altri progetti

• Commons

• Commons contiene file multimediali su Algoritmo di Prim

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica