23 Alberi di connessione minimi

Nella progettazione dei circuiti elettronici spesso è necessario rendere elettrica­mente equivalenti i pin di più componenti collegandoli insieme. Per interconnet­tere un insieme di n pin possiamo utilizzare un sistema di n — 1 fili conduttori,! ciascuno dei quali collega due pin. Fra tutti questi sistemi, di solito, viene preferito quello che usa la minor quantità di filo conduttore.

Possiamo modellare questo problema di cablaggio tramite un grafo connesso non orientato G = (V,E), dove V è l'insieme dei pin ed E è l'insieme delle possibili interconnessioni fra le coppie di pin; inoltre a ogni arco (u, v) e E § dato un peso w(u, v) che specifica il costo (quantità necessaria di filo conduttore! per collegare u e v. Vogliamo trovare un sottoinsieme aciclico T C E che collegi tutti i vertici, il cui peso totale

w(T) = E w{u,v) (u,w)eT

sia minimo. Poiché T è aciclico e collega tutti i vertici, deve anche formare una! bero, che è detto albero di connessione perché "connette" i l grafo G. Il problen di trovare l'albero T è detto problema dell'albero di connessione minimo.1

Figura 23.1 illustra un esempio di grafo connesso e i l suo albero di connessioni minimo.

In questo capitolo, esamineremo due algoritmi per risolvere il problema de] l'albero di connessione minimo: l'algoritmo di Kruskal e l'algoritmo di Prim.E| trambi gli algoritmi possono essere eseguiti nel tempo 0(E lg V) utilizzando dei normali heap binari. Utilizzando gli heap di Fibonacci, l'algoritmo di Primpuòe sere eseguito più rapidamente nel tempo 0(E + V lg V) , che è un migliorament] se |V | è molto più piccolo di \E\.

I due algoritmi sono algoritmi golosi (descritti nel Capitolo 16). A ogni passagi gio di un algoritmo deve essere fatta una delle tante scelte possibili. La strategi golosa prevede di fare la scelta che in un particolare momento è ritenuta la migli re. In generale, questa strategia non garantisce che vengano trovate le soluziol globalmente ottime per i problemi. Tuttavia, per il problema dell'albero dicof nessione minimo, è possibile dimostrare che alcune strategie golose forniscono! albero di connessione con peso minimo. Sebbene il presente capitolo possa ess| letto indipendentemente dal Capitolo 16, tuttavia i metodi golosi che ci accing ino a presentare sono un'applicazione classica dei concetti teorici introdotti] Capitolo 16.

Il termine "albero di connessione minimo" è un'abbreviazione di "albero di connessione di [ minimo." Non stiamo, per esempio, riducendo al minimo il numero di archi in T , perché tutt alberi di connessione hanno esattamente \V\ — 1 archi per il Teorema B.2.

23.1 Creare un albero di connessione minimo 481

I l Paragrafo 23.1 presenta un "algoritmo generico" per l'albero di connessione minimo che fa crescere un albero di connessione aggiungendo un arco alla volta. Il Paragrafo 23.2 descrive due modi di implementare questo algoritmo generico. Il primo algoritmo, sviluppato da Kruskal, è simile all'algoritmo per le compo­nenti connesse descritto nel Paragrafo 21.1. I l secondo algoritmo, dovuto a Prim, esimile all'algoritmo di Dijkstra per i cammini minimi (Paragrafo 24.4).

Figura 23.1 Un albero di connessione minimo per un grafo connesso. Sono indicali i pesi degli archi. Gl i archi di un albero di connessione minimo sono rappresentati su sfondo grigio. 11 peso totale dell'albero è 37. Questo albero di connessione minimo non è unico: eliminando l'arco (b, c) e sostituendolo con l'arco (a, fi) si ottiene un altro albero di connessione con peso 37.

passag- _:

. - 'W

.' SI strategia ; ' #

miglio- '* oluziom|| "Ij

di con­cono un a essere ' % :cingia- m lotti nel

23.1 Creare un albero di connessione minimo

Supponiamo di avere un grafo connesso non orientato G = (V, E) con una fun­zione peso w : E —+ R e di volere trovare un albero di connessione minimo per il grafo G. Entrambi gli algoritmi che consideriamo in questo capitolo usano un approccio goloso per risolvere i l problema, ma applicano in modo differente tale approccio.

Questa strategia golosa è sintetizzata nel seguente "algoritmo generico", che fa crescere l'albero di connessione minimo di un arco alla volta. L'algoritmo gestisce un insieme di archi A, conservando la seguente invariante di ciclo:

Prima di ogni iterazione, A è un sottoinsieme di qualche albero di connes­sione minimo.

A ogni passaggio, determiniamo un arco (u, v) che può essere aggiunto ad A senza violare questa invariante, nel senso che A\j{(u, v)} è anche un sottoinsieme di un albero di connessione minimo. Tale arco è detto arco sicuro per A, perché può essere tranquillamente aggiunto ad A preservando l'invariante.

'• GENERIC-MST (G/u;)

1 A^® 2 while A non forma un albero di connessione 3 do trova un arco (u, v) che è sicuro per A 4 A^Au{(u,v)} 5 return A

Utilizziamo l'invariante di ciclo nel modo seguente:

Inizializzazione: dopo la riga 1, l'insieme A soddisfa banalmente l'invariante di ciclo.

Conservazione: i l ciclo nelle righe 2-4 conserva l'invariante perché aggiunge soltanto archi sicuri.

Conclusione: tutti gli archi aggiunti ad A si trovano in un albero di connessione minimo, quindi l'insieme A restituito nella riga 5 deve essere un albero di connessione minimo.

482 Capitolo 23 - Alberi di connessione minimi

(a)

F igura 23.2 Due modi di vedere un taglio (S , V — S) del grafo illustrato nella Figura 23.1. (a)I vertici nell'insieme S sono rappresentati in nero, quelli nell'insieme V — S sono rappresentati in bianco. Gli archi che attraversano il taglio sono quelli che collegano i vertici bianchi con i vertici neri. L'arco (d, c) è l'unico arco leggero che attraversa il taglio. Un sottoinsieme A degli archi è rappresentato con uno sfondo grigio; notate che il taglio (S, V — S) rispetta A, perché nessun arco di A attraversa il taglio, (b) L o stesso grafo con i vertici nell'insieme S a sinistra e i vertici nell'insieme V — S a destra. Un arco attraversa il taglio se collega un vertice a sinistra con un vertice a destra.

La parte più diffìcile è, ovviamente, trovare un arco sicuro nella riga 3. Un arco sicuro deve esistere, perché quando viene eseguita la riga 3, l'invariante impone che ci sia un albero di connessione T tale che A C T. All'interno del corpo del ciclo while, A deve essere un sottoinsieme proprio di T , quindi deve esistere un arco (u, v) G T tale che (u, v) ^ A e (u, v) è un arco sicuro per A.

Nella parte restante di questo paragrafo, definiremo una regola (Teorema 23.1). per riconoscere gli archi sicuri. Il prossimo paragrafo descrive due algoritmi che applicano questa regola per trovare in maniera efficiente gli archi sicuri.

Innanzi tutto abbiamo bisogno di alcune definizioni. Un taglio (S, V - S) di un grafo non orientato G = (V, E) è una partizione di V. La Figura 23.2 illustra questo concetto. Si dice che un arco (u, v) e E attraversa il taglio (S, V - S) se;

una delle sue estremità si trova in S e l'altra in V — S. Si dice che un taglio rispetta un insieme A di archi se nessun arco di A attraver­

sa i l taglio. Un arco che attraversa un taglio è un arco leggero se i l suo peso è il minimo fra i pesi degli altri archi che attraversano il taglio. Notate che ci possono essere più archi leggeri che attraversano un taglio nel caso di pesi uguali. Più in generale, un arco è un arco leggero che soddisfa una data proprietà se i l suo peso è i l minimo di qualsiasi arco che soddisfa tale proprietà.

La nostra regola per riconoscere gli archi sicuri è definita dal seguente teorema.

Teorema 23.1 Sia G — (V, E) un grafo connesso non orientato con una funzione peso w a valori reali definita in E. Sia A un sottoinsieme di E che è contenuto in qualche albero di connessione minimo per G, sia (S, V — S) un taglio qualsiasi di G che rispetta A e sia (it, v) un arco leggero che attraversa (5, V — S). Allora, l'arco (u, v) è sicuro per A.

23.1 Creare un albero di connessione minimo 483

Dimostrazione Sia T un albero di connessione minimo che contiene A e sup­poniamo che T non contenga l'arco leggero (u,v), perché se Io contenesse, il teorema sarebbe dimostrato. Costruiremo un altro albero di connessione minimo T che include Au{(u, v)} utilizzando una tecnica "taglia e incolla", dimostrando così che (u, v) è un arco sicuro per A.

L'arco (u, v) forma un ciclo con gli archi nel cammino p che va da u a v in T, come è illustrato nella Figura 23.3. Poiché u e v si trovano su lati opposti del taglio (5, V — S), c'è almeno un altro arco in T nel cammino p che attraversa il taglio. Sia (x,y) uno di questi archi. L'arco (x,y) non appartiene ad A, per­ché il taglio rispetta A. Poiché (x,y) si trova nel cammino unico da u a v in T, eliminando (x,y), l'albero T si spezza in due componenti. Aggiungendo (u, v), le due componenti si ricongiungono per formare un nuovo albero di connessione r = T-{(x,y)}U{(u,v)}.

Dimostriamo adesso che T" è un albero di connessione minimo. Poiché (u, v) è un arco leggero che attraversa (5, V — S) e anche l'arco (x, y) attraversa questo taglio, allora w(u, v) < w(x, y). Quindi, si ha

w{T') = w(T) < w{T)

w(x, y) + w(u, v)

Ma T è un albero di connessione minimo, quindi w(T) < w(T') \ di conseguenza, anche T " deve essere un albero di connessione minimo.

Resta da dimostrare che (ti, v) è effettivamente un arco sicuro per A. Sappiamo che A C T', in quanto A C T e (x, y) £ A; quindi A U {(«,«)} C V. Di conseguenza, poiché T' è un albero di connessione minimo, (u, v) è un arco sicuro per A. •

Il Teorema 23.1 ci consente di capire meglio il funzionamento dell'algoritmo GENERIC-MST con un grafo connesso G — (V,E). Durante l'esecuzione del­l'algoritmo, l'insieme A è sempre aciclico; altrimenti un albero di connessione minimo che include A conterrebbe un ciclo, e ciò sarebbe una contraddizione. In qualsiasi momento dell'esecuzione dell'algoritmo, i l grafo GA = [V,A) è una foresta e ciascuna delle componenti connesse di GA è un albero. (Alcuni alberi possono contenere un solo vertice, come per esempio quando inizia l'algoritmo: A è vuoto e la foresta contiene | V | alberi, uno per ogni vertice.) Inoltre, qualsiasi arco sicuro (u,v) per A collega componenti distinte di GA, perché A U {(u,v)} deve essere aciclico.

Figura 23.3 L a dimostrazione del Teorema 23.1. I vertici in S sono neri; i vertici in V — S sono bianchi. Sono rappresentati gli archi nell'albero di connessione minimo T, mentre gli archi nel grafo G non sono rappresentati. Gli archi in A hanno uno sfondo grigio; (u,v) è un arco leggero che attraversa il taglio ( S , V - S). L'arco (x,y) è un arco nell'unico cammino p che va da u a v in T. Un albero di connessione minimo T' che contiene ( « , v) si ottiene eliminando l'arco (x, y) da T e aggiungendo l'arco (u, v).

484 Capitolo 23 - Alberi di connessione minimi

I l ciclo nelle righe 2-4 di GENERIC-MST viene eseguito | V | — 1 volte, in quan­to i \V\ — 1 archi di un albero di connessione minimo vengono determinati uno dopo l'altro. Inizialmente, quando A = 0, ci sono |V | alberi in GA e ogni itera­zione riduce questo numero di 1. Quando la foresta contiene un albero soltanto, l'algoritmo termina.

I due algoritmi descritti nel Paragrafo 23.2 usano il seguente corollario del Teorema 23.1.

Corollario 23.2 Sia G — (V, E) un grafo connesso non orientato con una funzione peso w a valori reali definita in E. Sia A un sottoinsieme di E che è contenuto in qualche albero di connessione minimo per G e sia C = (Vc,Ec) una componente connessa (un albero) nella foresta GA = (V, A). Se (u, v) è un arco leggero che collega C a qualche altra componente in GA, allora (u, v) è sicuro per A.

Dimostrazione II taglio (Ve, V — Ve) rispetta A e (u, v) è un arco leggero per questo taglio. Quindi, (u, v) è sicuro per A. i

Esercizi

23.1-1 Sia (u, v) un arco di peso minimo in un grafo G. Dimostrate che (u, v) appartiene a qualche albero di connessione minimo di G.

23.1-2 I l professor Sabatier propone i l seguente teorema come inverso del Teorema 23.1. Sia G = (V, E) un grafo connesso non orientato con una funzione peso w a valori reali definita in E. Sia A un sottoinsieme di E che è contenuto in qualche albero di connessione minimo per G, sia (S, V — S) un taglio qualsiasi di G che rispetta A e sia (u, v) un arco sicuro per A che attraversa (S, V — S). Allora, (u,v) è un arco leggero per il taglio. Dimostrate che i l professore si sbaglia fornendo un controesempio.

23.1-3 Dimostrate che, se un arco (u, v) è contenuto in qualche albero di connessione minimo, allora esso è un arco leggero che attraversa qualche taglio del grafo.

23.1-4 Fornite un semplice esempio di grafo connesso tale che l'insieme degli archi {(u,v) : esiste un taglio (5, V — S) tale che (u,v) sia un arco leggero che attraversa (S, V — S)} non formi un albero di connessione minimo.

23.1-5 Sia e un arco di peso massimo in qualche ciclo del grafo connesso G = (V,E). Dimostrate che esiste un albero di connessione minimo di G' — (V,E — {e}) che è anche un albero di connessione minimo di G. Ovvero esiste un albero di connessione minimo di G che non include e.

23.1-6 Dimostrate che un grafo ha un unico albero di connessione minimo se, per ogni taglio del grafo, esiste un unico arco leggero che attraversa i l taglio. Dimostrate che il contrario non è vero fornendo un controesempio.

23.2 Gli algoritmi di Kruskal e Prim 485

, in quan-inati uno gni itera-soltanto,

Ilario del.

u a valori re albero lessa (un lega C a

;gero per

•partiene

ma 23.1. eso ii: a qualche

l i G che a, (u, v) endo un

(.2-7 Dimostrate che, se tutti i pesi degli archi di un grafo sono positivi, allora qualsiasi ottoinsieme di archi che collega tutti i vertici e ha un peso totale minimo deve Isere un albero. Trovate un esempio per dimostrare che la stessa conclusione non vale se si ammette che qualche peso possa essere non positivo.

m-8 Sia T un albero di connessione minimo di un grafo G e sia L la lista ordinata dei pesi degli archi di T. Dimostrate che per qualsiasi altro albero di connessione minimo T' di G, la lista L è anche la lista ordinata dei pesi degli archi di T".

¿3.1-9 Èia T un albero di connessione minimo di un grafo G = (V, E) e sia V un sottoinsieme di V. Sia T" i l sottografo di T indotto da V e sia G' i l sottografo di G indotto da V. Dimostrate che, se T' è connesso, allora T" è un albero di connessione minimo di G'.

m-io Dato un grafo G e un albero di connessione minimo T, supponete di ridurre il peso di uno degli archi in T. Dimostrate che T è ancora un albero di connessione minimo per G. Più formalmente, sia T un albero di connessione minimo per G con i pesi degli archi dati dalla funzione peso w. Scegliete un arco (x, y) G T e

Jun numero positivo k e definite la funzione peso w' in questo modo:

w(u, v) se (u, v) ^ (x, y) w(x, y) - k se (u, v) = (x, y)

Dimostrate che T è un albero di connessione minimo per G con i pesi degli archi B'dati da io'.

m.i-ii * : Dato un grafo G e un albero di connessione minimo T, supponete di ridurre il peso di uno degli archi che non appartiene a T. Descrivete un algoritmo per trovare l'albero di connessione minimo nel grafo modificato.

ìessione afo.

; l i archi ero che

(V,E).

Ibero di

>er ogni, lostrate

23.2 Gli algoritmi di Kruskal e Prim

[ due algoritmi per gli alberi di connessione minimi descritti in questo paragrafo sono elaborazioni dell'algoritmo generico. Ciascuno di essi usa una regola speci­fica per determinare un arco sicuro nella riga 3 di GENERIC-MST. Nell'algoritmo di Kruskal l'insieme A è una foresta. L'arco sicuro aggiunto ad A è sempre un ar­co di peso minimo nel grafo che collega due componenti distinte. Nell'algoritmo

idi Prim l'insieme A forma un albero singolo. L'arco sicuro aggiunto ad A è sem­pre un arco di peso minimo che collega l'albero con un vertice che non appartiene all'albero.

Algoritmo di Kruskal

L'algoritmo di Kruskal si basa direttamente sull'algoritmo generico per gli alberi di connessione minimi che abbiamo descritto nel Paragrafo 23.1. Trova un arco sicuro da aggiungere alla foresta in costruzione scegliendo, fra tutti gli archi che collegano due alberi qualsiasi nella foresta, un arco (u,v) di peso minimo. Indi-

486 Capitolo 23 - Alberi di connessione minimi

(a)

(c)

(e)

(g)

(b)

(d)

(0

(h) 11 14

I

Figura 23.4 L'esecuzione dell'algoritmo di Kruskal con il grafo illustrato nella Figura 23.1. ! archi su sfondo grigio appartengono alla foresta A che è in costruzione. Gl i archi sono considera dall'algoritmo in ordine di peso crescente. Una freccia indica l'arco che è correntemente considerai nel passaggio dell'algoritmo. Se l'arco unisce due alberi distinti nella foresta, esso viene a alla foresta, fondendo così i due alberi in un unico albero.

chiamo con Ci e C% i due alberi che sono collegati da (M, i;). Poiché (M, V) I essere un arco leggero che collega Ci a qualche altro albero, il Corollario 23 implica che (u, v) è un arco sicuro per C\. L'algoritmo di Kruskal è un algoriti goloso, perché a ogni passaggio aggiunge alla foresta un arco con il minor pej possibile. La nostra implementazione dell'algoritmo di Kruskal è simile all'alg ritmo che calcola le componenti connesse che abbiamo descritto nel Paragrà] 21.1. Usa una struttura dati per insiemi disgiunti per mantenere vari insiemi;! sgiunti di elementi. Ogni insieme contiene i vertici di un albero della foresta c] rente. L'operazione F IND-SET(U) restituisce un rappresentante dell'insieme! contiene u. Quindi, possiamo determinare se due vertici u e v appartengono i lo stesso albero verificando se F IND-SET(U) è uguale a FIND-SET(W). L'unio degli alberi è effettuata dalla procedura U N I O N .

L'algoritmo di Kruskal opera come illustra la Figura 23.4. Le righe 1-3 i zializzano l'insieme A come un insieme vuoto e creano \V\ alberi, uno perog vertice. Gli archi in E vengono ordinati in senso non decrescente rispetto aff

23.2 Gli algoritmi di Kruskal e Prim 487

so nella riga 4. I l ciclo for nelle righe 5-8 verifica, per ogni arco (u, v), se le estremità u tv appartengono allo stesso albero; in caso affermativo, l'arco (u, v) non può essere aggiunto alla foresta senza generare un ciclo, quindi l'arco viene scartato. Altrimenti i due vertici appartengono ad alberi differenti. In questo caso, l'arco (u,v) viene aggiunto ad A nella riga 7 e i vertici nei due alberi vengono

si nella riga 8.

MST-KRUSKAL(G,W)

2 for ogni vertice v G V [G] 3 do M A K E - S E T ( ( ; )

;4 ordina gli archi di E in senso non decrescente rispetto al peso w | for ogni arco (u, v) G E preso in ordine di peso non decrescente 6 do if F I N D - S E T ( U ) ^ FlND-SET(t>)

then A t - i U {(u,v)} 8 U N I O N ( U , V) 9 return A

Il tempo di esecuzione dell'algoritmo di Kruskal per un grafo G = (V,E) di­spende dall'implementazione della struttura dati per gli insiemi disgiunti. Utilizze­remo l'implementazione della foresta di insiemi disgiunti descritta nel Paragrafo ¡21.3 con le euristiche dell'unione per rango e della compressione dei cammini, perché è l'implementazione asintoticamente più veloce fra quelle conosciute. L ' i -nizializzazione dell'insieme A nella riga 1 richiede un tempo 0(1); i l tempo per ordinare gli archi nella riga 4 è 0(E lg E) (valuteremo subito dopo i l costo delle

I y | operazioni M A K E - S E T del ciclo for nelle righe 2-3). Il ciclo for nelle ri­ghe 5-8 esegue 0(E) operazioni F I N D - S E T e U N I O N sulla foresta degli insiemi

488 Capitolo 23 - Alberi di connessione minimi

disgiunti. Tenendo conto anche delle | V | operazioni M A K E - S E T , si ottiene un tempo totale pari a 0((V + E) a(V)), dove a è la funzione (con crescita molto lenta) definita nel Paragrafo 21.4. Poiché supponiamo che G sia un grafo con­nesso, abbiamo \E\ > \V\ — 1, e quindi le operazioni con gli insiemi disgiunti richiedono un tempo 0(E a(V)). Inoltre, poiché a ( | V | ) = 0 ( lg V) = 0(\gE), il tempo di esecuzione totale dell'algoritmo di Kruskal è O(EìgE). Osservando che \E\ < \V\2, si ha l g | £ | = 0(lgV); quindi possiamo ridefinire il tempo di esecuzione dell'algoritmo di Kruskal come O(EìgV).

Algoritmo di Prim

Come l'algoritmo di Kruskal, anche l'algoritmo di Prim è un caso speciale del­l'algoritmo generico per gli alberi di connessione minimi descritto nel Paragrafo 23.1. L'algoritmo di Prim opera in modo molto simile all'algoritmo di Dijkstra per trovare i cammini minimi in un grafo, come vedremo nel Paragrafo 24.4. L'al­goritmo di Prim ha la proprietà che gli archi nell'insieme A formano sempre un albero singolo. Come illustra la Figura 23.5, l'albero inizia da un arbitrario ver­tice radice r e si sviluppa fino a coprire tutti i vertici in V. A ogni passaggio viene aggiunto all'albero A un arco leggero che collega A con un vertice isolato di GA — {V, A). Per i l Corollario 23.2, questa regola aggiunge soltanto gli archi-che sono sicuri per A; cosicché, quando l'algoritmo termina, gli archi in A for­mano un albero di connessione minimo. Questa strategia è golosa perché l'albero, cresce includendo a ogni passaggio un arco che contribuisce con la quantità più piccola possibile a formare i l peso dell'albero.

La chiave per implementare con efficienza l'algoritmo di Prim consiste nel semi* plificare la scelta di un nuovo arco da aggiungere all'albero formato dagli archi in A. Nel seguente pseudocodice, il grafo connesso G e la radice r dell'albero di connessione minimo da costruire sono gli input per l'algoritmo. Durante l'esecu­zione dell'algoritmo, tutti i vertici che non si trovano nell'albero risiedono in una* coda di min-priorità Q basata su un campo key. Per ogni vertice v, key[v] è il peso minimo di un arco qualsiasi che collega v a un vertice nell'albero; per con­venzione, key[v] = oo se tale arco non esiste. I l campo n[v] indica il padre di v nell'albero. Durante l'esecuzione dell'algoritmo, l'insieme A di GENERIC-MST è mantenuto implicitamente come

A — [(v, n[v]) :veV-{r}-Q}

Quando l'algoritmo termina, la coda di min-priorità Q è vuota; l'albero di con­nessione minimo A per G è quindi

A = {(V,TT[V\) : v e V - {r}}

M S T - P R I M ( C 7 , w,r)

1 for ogni u e V[G] 2 do key[u] <— oo 3 n[u] <— N I L 4 key[r] *- 0 5 Q+-V[G]

23.2 G l i algoritmi di K r u s k a l e Pr im 489

(b)

(d)

(f)

! (g) (h)

Figura 23.5 L'esecuzione dell'algoritmo di Prim con il grafo illustrato nella Figura 23.1.11 vertice radice è a. Gli archi con sfondo grigio appartengono all'albero in costruzione; i vertici dell'albero sono di colore nero. A ogni passaggio dell'algoritmo, i vertici dell'albero determinano un taglio del grafo e un arco leggero che attraversa il taglio viene aggiunto all'albero. Nel secondo passaggio, per esempio, l'algoritmo può scegliere di aggiungere all'albero l'arco (b, c) o l'arco (a, h), in quanto entrambi sono archi leggeri che attraversano il taglio.

6 vvhileQ^0 do u <— E X T R A C T - M I N ( Q )

for ogni v € Adj [u] do if v G Q and w(u, v) < key[v]

then 7r[v] <— u key[v] <— w(u, v)

490 Capito lo 23 - Alber i di connessione minimi

L'algoritmo di Prim opera come illustra la Figura 23.5. Le righe 1-5 impostano-la chiave di ciascun vertice a oo (ad eccezione della radice r, la cui chiave è impostata a 0; in questo modo la radice sarà il primo vertice ad essere elaborato), assegnano al padre di ciascun vertice il valore N I L e inizializzano la coda di min-priorità Q in modo che contenga tutti i vertici. L'algoritmo conserva la seguente invariante di ciclo composta da tre parti:

Prima di ogni iterazione del ciclo while (righe 6-11):

1. A = {{v,n[v}) .ve V- {r}-Q}.

2. I vertici già inseriti nell'albero di connessione minimo sono quelli che I appartengono aV — Q.

3. Per ogni vertice v G Q, se ir[v] ^ N I L , allora key[v] < oo e key[v] è il I peso di un arco leggero (v, n[v]) che collega v a qualche vertice che si "| trova già nell'albero di connessione minimo.

La riga 7 identifica un vertice u G Q incidente su un arco leggero che attraversi il taglio (V — Q,Q) (ad eccezione della prima iterazione, nella quale u = rpe la riga 4). Quando il vertice u viene eliminato dall'insieme Q, viene aggirai all'insieme V — Q dei vertici dell'albero, quindi (u, n[u\) viene aggiunto ad .4. ciclo for nelle righe 8-11 aggiorna i campi key e 7r di qualsiasi vertice v adiacen a u, ma che non appartiene all'albero. L'aggiornamento conserva la terza pari dell'invariante di ciclo.

Le prestazioni dell'algoritmo di Prim dipendono dal modo in cui viene impljjf mentata la coda di min-priorità Q. Se Q è implementata come un min-heap bjf nario (vedere il Capitolo 6), possiamo utilizzare la procedura BuiLD-MlN-HEAP per eseguire nel tempo 0(V) l'inizializzazione nelle righe 1-5. Il corpo del eie) while viene eseguito |F | volte e, poiché ogni operazione E X T R A C T - M I N richie­de un tempo 0( lg V) , il tempo totale per tutte le chiamate di EXTRACT-MIN ? J

O ( V l g V ) . I l ciclo for (righe 8-11) viene eseguito O(E) volte complessivamente, inqu

to la somma delle lunghezze di tutte le liste di adiacenza è 2 \ E\. All'interno d ciclo for, il test che verifica l'appartenenza a Q nella riga 9 può essere imp mentato in tempo costante mantenendo un bit per ciascun vertice che indica un vertice appartiene o no a Q, e aggiornando il bit quando il vertice viene e minato da Q. L'assegnazione nella riga 11 richiede implicitamente un'operazio DECREASE-KEY sul min-heap, che può essere implementata con un min-h binario nel tempo 0 ( lg V).

Quindi, il tempo totale dell'algoritmo di Prim è 0(V\gV + EìgV) O(EìgV), che è asintoticamente uguale a quello della nostra implementazio dell'algoritmo di Kruskal.

I l tempo di esecuzione asintotico dell'algoritmo di Prim può essere migliorai utilizzando gli heap di Fibonacci. Nel Capitolo 20 abbiamo visto che, se |V| ef menti sono organizzati in un heap di Fibonacci, è possibile eseguire un'operazio E X T R A C T - M I N nel tempo ammortizzato O( lgV) e un'operazione DECREA K E Y (per implementare la riga 11) nel tempo ammortizzato 0(1). Quindi utilizziamo un heap di Fibonacci per implementare la coda di min-priorità Q, tempo di esecuzione dell'algoritmo di Prim migliora diventando 0(E + V lg V