Algoritmo di Prim

Algoritmo di Prim
Esecuzione dell'algoritmo di Prim
Classe	Albero ricoprente minimo
Struttura dati	Grafo
Caso peggiore temporalmente	$O(|E|+|V|\log |V|)$

L'algoritmo di Prim è un algoritmo ottimo utilizzato in teoria dei grafi, informatica e ricerca operativa per determinare gli alberi di supporto minimi di un grafo non orientato e con pesi non negativi.

Storia

Fu originariamente sviluppato nel 1930 dal matematico ceco Vojtěch Jarník e successivamente, nel 1957, fu indipendentemente sviluppato dall'informatico Robert C. Prim. Nel 1959 venne riscoperto da Edsger Dijkstra. A causa dei contributi di questi studiosi lo si trova spesso citato come algoritmo DJP (Dijkstra, Jarnìk, Prim), Algoritmo di Jarnik o algoritmo di Prim-Jarnik.

Caratteristiche

Le caratteristiche dell'algoritmo di Prim possono essere sintetizzate nei seguenti punti:

• Algoritmo greedy: perché valuta di volta in volta le soluzioni localmente migliori senza mettere in discussione le scelte precedenti.
• Algoritmo esatto: perché fornisce una soluzione precisa per ogni istanza del problema senza effettuare arrotondamenti o imprecisioni di altra natura.
• Algoritmo ottimo: perché presenta la soluzione migliore (o, a parità di qualità di soluzioni, una tra le soluzioni migliori).

Descrizione

Per la descrizione dell'algoritmo si assume che 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.

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 V (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})$.

Se la coda con priorità è realizzata con Heap di Fibonacci il tempo di esecuzione può essere ulteriormente migliorato. Infatti, il tempo di insert e decreaseKey si riduce $O(1)$, ammortizzato dalle deleteKey con costo $O(\log {V})$.

L'implementazione dell'algoritmo di Prim con Fibonacci Heap è la più efficiente ottenibile, infatti il costo di esecuzione è $O(E+V\cdot \log {V})$. Per averne conferma, si consideri un grafo completamente connesso ($E=O(V^{2})$) e si confrontino i tempi di esecuzione.

L'algoritmo di Prim è un perfetto esempio di come strutture dati efficienti consentano di risolvere efficientemente un problema.

Esempio

Immagine	Nodi processati	Lati Disponibili	Nodi nella coda	Descrizione
	{}		{A,B,C,D,E,F,G}	Grafo direzionato originale, i numeri sui lati indicano il loro peso. Come punto di inizio si può scegliere un vertice arbitrario e qui si procederà scegliendo il vertice D. Note sulla colonna "immagine": in verde verranno indicati i nodi e i lati che sono stati scelti per rientrare nella soluzione. in blu verranno indicati i lati che sono in corso di valutazione in azzurro verrà indicata la scelta corrente da aggiungere alla soluzione parziale. in nero verranno indicati i lati che non rientrano nella soluzione o che non vengono considerati in quanto collegati a nodi non ancora raggiungibili dall'attuale soluzione o in quanto collegati a nodi già raggiunti da altri lati con costo inferiore.
	{D}	{D,A} = 5 V {D,B} = 9 {D,E} = 15 {D,F} = 6	{A,B,C,E,F,G}	I vertici A, B, E e F sono quelli connessi direttamente a D. A dista 5, B dista 9, E dista 15, F dista 6. Il vertice più vicino a D è A e pertanto viene selezionato assieme al lato AD.
	{A,D}	{D,B} = 9 {D,E} = 15 {D,F} = 6 V {A,B} = 7	{B,C,E,F,G}	Il vertice successivo da scegliere sarà quello più vicino a D oppure ad A. B dista 9 da D e 7 da A, E dista 15 da D, e F dista 6 da D. Tra tutti i vertici, F è quello più vicino e quindi viene scelto assieme al lato DF che lo congiunge.
	{A,D,F}	{D,B} = 9 {D,E} = 15 {A,B} = 7 V {F,E} = 8 {F,G} = 11	{B,C,E,G}	L'algoritmo continua come nei passi precedenti. Il lato più vicino a D, A o F è da scegliere tra B, E o G. Osservando i pesi, risulta essere B che dista solo 7 da A e pertanto viene scelto assieme al lato congiungente AB.
	{A,B,D,F}	{B,C} = 8 {B,E} = 7 V {D,B} = 9 cycle {D,E} = 15 {F,E} = 8 {F,G} = 11	{C,E,G}	In questo caso possiamo scegliere tra C, E, e G. Il vertice C dista 8 da B, E dista 7 da B, e G dista 11 da F. Il vertice E è il più vicino quindi scegliamo il vertice E assieme al lato BE.
	{A,B,D,E,F}	{B,C} = 8 {D,B} = 9 cycle {D,E} = 15 cycle {E,C} = 5 V {E,G} = 9 {F,E} = 8 cycle {F,G} = 11	{C,G}	Gli unici vertici disponibili sono C e G. C dista 5 da E, e G dista 9 da E. C è il più vicino e viene scelto assieme al lato EC.
	{A,B,C,D,E,F}	{B,C} = 8 cycle {D,B} = 9 cycle {D,E} = 15 cycle {E,G} = 9 V {F,E} = 8 cycle {F,G} = 11	{G}	Il vertice G è l'unico vertice rimanente. Dista 11 da F e 9 da E. E è il più vicino e quindi scegliamo G assieme al lato EG.
	{A,B,C,D,E,F,G}	{B,C} = 8 cycle {D,B} = 9 cycle {D,E} = 15 cycle {F,E} = 8 cycle {F,G} = 11 cycle	{}	Tutti i vertici sono stati selezionati e l'albero di supporto a costo minimo è mostrato in verde. In questo caso, il costo è 39.

Applicazioni

All'interno della teoria dei grafi trova applicazione nell'individuazione di grafi e componenti connesse. Possiede anche molte applicazioni pratiche non direttamente legate alla teoria dei grafi. (es. viene utilizzato per sviluppare labirinti).

Varie

• Può essere utilizzato anche su grafi orientati e con peso non negativo ma in questa situazione perde la caratteristica di essere un algoritmo ottimo. Per queste tipologie di grafi, l'algoritmo di Prim presenta una soluzione ma non è quella ottima.

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-0-89871-187-5, OCLC 10120539.

Voci correlate

• Algoritmo di Kruskal
• Algoritmo di Dijkstra
• Algoritmo di Floyd-Warshall

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sull'Algoritmo di Prim