Lezione 13
Strutture dati per insiemi disgiunti
Alberi di copertura minimi
Sommario
• Strutture dati per insiemi disgiunti
• Determinazione delle componenti connesse di un
grafo
• Alberi di copertura minimi per grafi pesati
– Algoritmo di Kruskal
– Algoritmo di Prim
Strutture dati per insiemi disgiunti
• In alcune applicazioni siamo interessati a mantenere
gruppi distinti di oggetti
• per queste applicazioni risultano importanti
operazioni quali: determinare a quale insieme
appartiene un oggetto e unire più insiemi
Insiemi disgiunti
• Una struttura dati per insiemi disgiunti mantiene una
collezione S={S1,S2,…,Sk} di insiemi dinamici
disgiunti
• ogni insieme Si è identificato da un rappresentante
• un rappresentante per un insieme Si può essere
– un qualsiasi membro dell’insieme Si
– un membro particolare dell’insieme Si
Rappresentante di un insieme
• Se il rappresentante di un insieme è un qualunque
elemento allora:
– a fronte di una serie di operazioni di ricerca del
rappresentante di uno stesso insieme deve sempre essere
restituito lo stesso rappresentante
– solo nel caso in cui l’insieme venga modificato tramite
l’unione con un altro insieme l’elemento rappresentante può
cambiare
Rappresentante di un insieme
• Il rappresentante può essere un elemento specifico
dell’insieme
• si devono definire delle caratteristiche degli insiemi e
una regola per caratterizzare il rappresentante
• Ex: l’elemento più piccolo/grande di un insieme
Operazioni
• Dato un elemento x le operazioni definibili su una
struttura dati per insiemi disgiunti sono:
– Make-Set(x)
– Union(x,y)
– Find-Set(x)
Make-Set
• Crea un nuovo insieme il cui unico membro e
rappresentante è x.
• Dato che gli insiemi sono disgiunti si deve garantire
che x non appartenga già ad un altro insieme
Union
• Unisce due insiemi Sx e Sy che contengono gli
elementi x e y.
• Si deve garantire che gli insiemi siano disgiunti.
• L’elemento rappresentante può essere un qualsiasi
elemento dell’insieme unione Sx  Sy .
• Di solito si utilizza il rappresentante di Sx o di Sy come
rappresentante finale.
• Dato che gli insiemi sono disgiunti l’operazione di
unione deve distruggere i vecchi insiemi Sx e Sy.
Find-Set
• Restituisce il rappresentante dell’unico insieme
contenete x
Implementazione tramite
liste concatenate
• Ogni insieme viene rappresentato con una lista
concatenata
• il primo oggetto di una lista viene utilizzato come
rappresentante dell’insieme
• ogni elemento nella lista contiene:
– un oggetto
– un puntatore all’elemento successivo
– un puntatore al rappresentante
Visualizzazione
c
h
e
b
Operazioni
• Le operazioni Make-Set e Find-Set sono semplici e
richiedono un tempo O(1):
– Make-Set(x): crea una nuova lista concatenata in cui l’unico
oggetto è x e inizializza il puntatore al rappresentante a x
stesso
– Find-Set(x): restituisce il puntatore da x al rappresentante
• L’operazione Union(x,y) richiede più tempo:
• la versione più semplice è quella in cui si appende la
lista contentente x alla lista contentente y
• l’elemento rappresentante per l’unione è il
rappresentante della lista contenente y
Visualizzazione dell’unione
c
h
e
b
f
g
x
f
g
d
z
y
d
z
Union(x,y)
c
h
e
b
Costo dell’unione
• L’operazione di Union richiede la modifica di tutti i
puntatori al rappresentante dell’oggetto x e questo
richiede in media un tempo lineare nella lunghezza
della lista contentente x
• infatti se si creano n insiemi di un unico oggetto e si
uniscono nel seguente ordine:
–
–
–
–
–
Union(x1,x2)
Union(x2,x3)
Union(x3,x4)
Union(x4,x5)
Union(x5,x6)
• si devono fare 1, 2, 3,…,n modifiche ai puntatori, per
un totale di O(n2) operazioni
Eurisitica peso
• Una strategia per diminuire il costo dell’operazione
Union consiste nel:
– memorizzare l’informazione della lunghezza della lista
– appendere la lista più corta a quella più lunga
• risulta poi facile mantenere l’informazione di
lunghezza della lista dopo l’unione in tempi O(1)
Implementazione tramite
foreste
• Si può realizzare una implementazione più veloce
delle strutture dati per insiemi disgiunti
rappresentando ogni insieme tramite un albero
radicato
• ogni nodo dell’albero contiene l’oggetto e un
puntatore al padre
• l’oggetto rappresentante è l’oggetto contenuto nella
radice dell’albero
• la radice ha come padre un puntatore a se stessa
Visualizzazione
f
c
h
b
e
f
d
g
d
c
h
b
e
g
Operazioni
• Make-Set(x): crea un albero con un unico nodo x e
con padre se stesso
• Find-Set(x): risale la lista dei padri di x fino a trovare
la radice e restituisce la radice come oggetto
rappresentante
• Union-Set(x,y): determina le radici dei due alberi
contenteti x e y e fa diventare la radice dell’albero
contentente x un figlio della radice dell’albero
contentente y
Euristiche
• Di per sé la rappresentazione tramite foreste non è
più veloce della rappresentazione con liste, ma su
questa rappresentazione è possibile introdurre delle
euristiche che rendono questa implementazione la
più veloce conosciuta
• Euristiche:
– unione per rango
– compressione dei cammini
Euristica del rango
• Definizioni:
• Si mantiene una informazione aggiuntiva per ogni
nodo: il rango memorizzata nell’attributo rank[x]
• il rango di un nodo è il limite superiore all’altezza di x,
ovvero il numero di archi del cammino più lungo fra x
e una foglia sua discendente
Euristica del rango
• E’ simile all’unione pesata con le liste concatenate
• L’idea è di fare sì che mediamente l’albero più basso
diventi un sottoalbero di quello più alto
• ovvero che la radice dell’albero più basso punti alla
radice dell’albero più alto in una operazione di Union
Euristica del rango
• Nota:il rango non è l’altezza dell’albero, ma solo un
limite superiore.
• Questo rende più semplice la sua manipolazione e
meno costoso il suo mantenimento.
• In particolare se gli alberi sono manipolati in modo da
diminuire l’altezza di un nodo, questo non si riflette
sul rango che rimane inalterato
Euristica della
compressione dei cammini
• La compressione dei cammini viene usata per le
operazioni Find-Set(x)
• l’idea è di modificare un albero in modo che in
ricerche successive di x l’elemento rappresentante
venga restituito in O(1)
• per fare questo si modifica il puntatore al padre di
ogni nodo sul cammino da x alla radice perché punti
direttamente alla radice
Visualizzazione compressione dei
cammini per l’operazione Find-Set(f)
b
e
d
f
b
f
d
e
Visualizzazione compressione dei
cammini per l’operazione Find-Set(d)
b
b
e
d
d
f
f
e
Spiegazione intuitiva
• Quando viene creato un nuovo insieme con MakeSet il rango iniziale dell’unico nodo nell’albero è 0
• l’esecuzione dell’operazione Find-Set non modifica i
ranghi
– infatti non cambia il limite superiore dell’altezza (riduce
l’altezza degli alberi, non la incrementa)
• per l’operazione di Union
– si rende la radice con rango maggiore padre di quella con
rango minore; il rango della radice non cambia
– in caso di eguaglianza si sceglie arbitrariamente una delle
due radici come padre; il rango della radice aumenta di 1
Pseudocodice
Make-Set(x)
1 p[x]  x
2 rank[x]  0
Union(x,y)
1 Link(Find-Set(x),Find-Set(y))
Link(x,y)
1 if rank[x] > rank[y]
2 then p[y]  x
3 else p[x]  y
4
if rank[x]=rank[y]
5
then
rank[y]  rank[y]+1
Pseudocodice
Find-Set(x)
1 if x  p[x]
2 then p[x]  Find-Set(p[x])
3 return p[x]
Find-Set
• La procedura Find-Set è una procedura a due
passate:
– nella prima si risale il cammino di accesso per determinare
la radice
– nella seconda si discende e si aggiornano tutti i nodi in modo
che puntino alla radice
• se x=p[x], ovvero siamo arrivati alla radice, la
procedura restituisce p[x]. Questo è il passo base
della ricorsione.
• altrimenti si chiama ricorsivamente la procedura
aspettando di determinare e poi restituire il puntatore
alla radice
Analisi
• L’uso delle euristiche dell’unione per rango e della
compressione dei cammini con la rappresentazione
di foreste di insiemi disgiunti porta ad una efficienza
pari a O(n) in tutti i casi di applicazioni pratiche con n
pari al numero di operazioni Make,Union,Find che si
vogliono eseguire sugli insiemi disgiunti.
Componenti connesse di un grafo
• Una applicazione delle strutture dati per insiemi
disgiunti consiste nella determinazione delle
componenti connesse di un grafo non orientato
• una componente connessa di un grafo G è un
sottografo G’ tale per cui esiste un cammino semplice
(tutti i vertici del cammino sono distinti) per ogni
coppia di vertici di G’
Visualizzazione di componenti connesse
di un grafo non orientato
a
b
e
c
d
g
f
h
i
j
Idea intuitiva
• L’idea è di partire da componenti connesse costituite
da un unico vertice
• ogni componente connessa viene poi unita ad altre
componenti connesse tramite l’operazione di Union
• l’unione fra due insiemi viene fatta se esiste un arco
fra due qualsiasi vertici in tali insiemi
Idea intuitiva
• Infatti se abbiamo che:
– un vertice x è raggiungibile da ogni altro vertice in un
insieme Sx
– e analogamente per un vertice y in un insieme Sy
– ed esiste un arco che collega x e y
• allora ne consegue che l’unione fra Sx e Sy è un
insieme connesso dato che da ogni elemento in Sx si
può adesso raggiungere un qualsiasi elemento in Sy
tramite l’arco (x,y) e viceversa
Pseudocodice
Connected-Components(G)
1 for ogni vertice v in V[G]
2 do
Make-Set(v)
3 for ogni arco (u,v) in E[G]
4 do
if Find-Set(u) Find-Set(v)
5
then Union(u,v)
Esempio
Arco
(b,d)
(e,g)
(a,c)
(h,i)
(a,b)
(e,f)
(b,c)
a
b
e
c
d
g
f
Collezione insiemi disgiunti
a
b
c
d
e
a
b,d
c
e
a
b,d
c
e,g
a,c
b,d
e,g
a,c
b,d
e,g
a,c,b,d
e,g
a,c,b,d
e,g,f
a,c,b,d
e,g,f
h
i
f
f
f
f
f
f
g
g
h
h
h
h
h,i
h,i
h,i
h,i
i
i
i
i
Albero di copertura minimo
• Un problema di notevole importanza consiste nel
determinare come interconnettere fra di loro diversi
elementi minimizzando certi vincoli sulle connessioni
• un esempio classico è quello della progettazione dei
circuiti elettronici dove si vuole minimizzare la
quantità di filo elettrico per collegare fra loro i morsetti
di diversi componenti
Albero di copertura minimo
• il problema può essere modellato con un grafo non
orientato e connesso in cui le interconnessioni sono
archi pesati (u,v) e dove il peso specifica il costo per
connettere u con v
• la soluzione del problema consiste nella
determinazione di un sottografo aciclico T E che
connetta tutti i vertici in modo da minimizzare il peso
totale w(t)=(u,v)T w(u,v)
• dato che T è aciclico e collega tutti i vertici deve
essere un albero
• tale albero è chiamato albero di copertura minimo o
minimum spanning tree MST
Esempio
8
b
c
4
8
d
9
2
11
a
7
i
7
h
6
g
1
14
4
f
2
10
e
Unicità
• L’albero di copertura minimo non è unico
• ad esempio si possono dare due albero di copertura
minimi per il grafo in esame
8
4
b
11
a
8
h
2
i
7
1
8
7
c
6
g
d
14
4
2
9
f
10
4
e
b
11
a
8
h
2
i
7
1
7
c
6
g
d
14
4
2
9
f
10
e
Algoritmo generico
• Verranno illustrati due algoritmi di tipo “greedy” o
golosi:
– Algoritmo di Kruskal
– Algoritmo di Prim
• L’approccio greedy consiste nello scegliere fra più
alternative quella più conveniente sul momento
• Nota: in generale non è detto che in ogni tipo di
problema questo porti ad una soluzione globalmente
ottima.
• Per la soluzione del problema dell’albero di copertura
minima una soluzione greedy coincide con una
soluzione globalmente ottima
Arco sicuro
• L’idea è di accrescere un sottoinsieme A di archi di un
albero di copertura aggiungendo un arco alla volta
• Ad ogni passo si determina un arco che può essere
aggiunto ad A mantenendo la proprietà per A di
essere un sottoinsieme di archi di un albero di
copertura
• Un arco di questo tipo è detto arco sicuro
Pseudocodice
Generic-MST(G,w)
1 A  
2 while A non forma un albero di copertura
3 do
trova un arco sicuro (u,v)
4
A  A  {(u,v)}
5 return A
Algoritmi concreti
• Per poter implementare l’algoritmo generico abbiamo
bisogno di determinare gli archi sicuri
• per caratterizzare gli archi sicuri dobbiamo introdurre
alcune definizioni:
– un taglio (S,V-S) di un grafo non orientato G=(V,E) è una
partizione di V
– un arco attraversa il taglio se uno dei suoi estremi è in S e
l’altro è in V-S
– un taglio rispetta un insieme di archi A se nessun arco di A
attraversa il taglio
– un arco leggero è un arco con peso minimo
Visualizzazione dei concetti
8
b
c
4
8
d
9
2
11
a
7
Arco leggero che
attraversa il taglio
i
7
h
6
g
1
Insieme A: archi in grigio
il taglio rispetta A
14
4
f
2
e
10
Taglio
Archi sicuri
• La regola per riconoscere gli archi sicuri è data dal
seguente:
• Teorema:
– Sia G=(V,E) un grafo non orientato e connesso con una
funzione peso w a valori reali definita su E. Sia A un
sottoinsieme di E contenuto in un qualche albero di
copertura minimo per G. Sia (S,V-S) un qualunque taglio che
rispetta A. Sia (u,v) un arco leggero che attraversa il taglio.
Allora l’arco (u,v) è sicuro per A
Visualizzazione
arco non sicuro perché taglio non rispetta
8
4
11
a
8
8
4
b
11
a
8
h
2
i
7
1
7
c
6
g
d
14
4
2
9
f
b
2
i
7
h
7
c
6
9
e
14
4
g
1
d
f
2
10
Arco sicuro
e
10
8
4
b
11
a
8
h
2
i
7
1
Arco non sicuro
7
c
6
g
d
14
4
2
9
f
10
e
Visualizzazione
arco non sicuro perché non leggero
8
4
11
a
8
8
4
b
11
a
8
h
2
i
7
1
7
c
6
g
d
2
f
c
2
i
7
h
6
9
e
14
4
g
1
d
10
f
2
9
14
4
b
7
Arco sicuro
e
10
8
4
b
11
a
8
h
2
i
7
1
Arco non sicuro
7
c
6
g
d
14
4
2
9
f
10
e
Archi sicuri
• Dimostrazione:
–
–
–
–
sia T l’albero di copertura minimo che contiene A
l’arco (u,v) o appartiene a T, e quindi è sicuro per A
oppure non appartiene a T:
in questo caso faremo vedere che sostituendo un arco in T
con il nuovo arco (u,v) otteniamo un T’ che è sempre un
albero di copertura minimo
• infatti deve esserci un arco (x,y) di T che attraversa il taglio
perché T è un insieme connesso e quindi deve esserci un
percorso fra u e v che sono da parti opposte del taglio
• inoltre (x,y) non è in A perché il taglio rispetta A
• se costruisco T’ come T-(x,y)+(u,v) ho creato un insieme
connesso con costo complessivo  di T che copre tutti i vertici e
che ha costo minimo e quindi deve essere un albero di
copertura minimo
• (in pratica (u,v) deve essere un arco con costo equivalente a
(x,y))
Archi sicuri
– se T’ è un albero di copertura minimo allora dato che A è
compreso in T e che (x,y) non era in A allora A è anche
compreso in T’
– infatti l’unico cambiamento da T in T’ è stato solo per l’arco
(x,y) e (u,v) che non sono in A, gli altri archi sono rimasti
inalterati
– di conseguenza aggiungere (u,v) ad A mantiene A un
sottoinsieme dell’albero di copertura (T’ questa volta) e
dunque è un arco sicuro per A
Archi sicuri
• Corollario:
– Sia G=(V,E) un grafo non orientato e connesso con una
funzione peso w a valori reali definita su E. Sia A un
sottoinsieme di E contenuto in un albero di copertura minimo
per G e sia C una componente connessa (un albero) nella
foresta GA=(V,A). Se (u,v) è un arco leggero che connette C
a qualche altra componente in GA allora (u,v) è sicuro per A
• Dimostrazione:
– il taglio (C,V-C) rispetta A: quindi l’arco leggero (u,v) è un
arco sicuro per A per il teorema precedente
Algoritmo di Kruskal
• L’idea dell’algoritmo di Kruskal è di ingrandire
sottoinsiemi disgiunti dell’albero di copertura minimo
connettendoli fra di loro fino ad avere l’albero
complessivo
• in particolare si individua un arco sicuro da
aggiungere alla foresta scegliendo un arco (u,v) di
peso minimo tra tutti gli archi che connettono due
distinti alberi (componenti connesse) della foresta
• l’algoritmo è greedy perché ad ogni passo si
aggiunge alla foresta un arco con il peso minore
possibile
Algoritmo di Kruskal
• L’idea è che, come richiesto dall’algoritmo astratto:
– ogni componente connessa in A appartiene all’albero di
copertura
– unendo componenti connesse tramite archi leggeri (per il
corollario) si stanno aggiungendo archi sicuri
– ad ogni fusione di componenti connesse stiamo espandendo
A
– si può continuare fino a quando non si sono acquisiti tutti i
vertici del grafo
Implementazione
• L’algoritmo presentato è simile a quello usato per
calcolare le componenti connesse
• si usa una struttura dati per insiemi disgiunti
• ogni insieme contiene i vertici di un albero della
foresta corrente
• si può determinare se due vertici appartengono allo
stesso albero verificando l'eguaglianza degli elementi
rappresentanti restituiti da Find-Set
• si fondono due alberi tramite la Union
Pseudocodice Kruskal
MST-Kruskal(G,w)
1 A  
2 for ogni vertice v in V[G]
3 do
Make-Set(v)
4 ordina gli archi di E per peso w non decrescente
5 for ogni arco (u,v) in E in ordine di peso non decrescente
6 do
if Find-Set(u) Find-Set(v)
5
then
A  A  {(u,v)}
6
Union(u,v)
7 return A
Spiegazione dello pseudocodice
• Le linee 1-3 inizializzano l’insieme A con l’insieme
vuoto e creano |V| alberi, uno per ogni vertice
• la linea 4 ordina gli archi per peso
• nelle linee 5-8 il ciclo for controlla che i vertici di ogni
arco appartengano ad alberi diversi
• in caso affermativo
– l’arco viene aggiunto ad A
– la linea 8 fonde i due alberi in un unico insieme
– Nota: se i vertici appartenessero allo stesso albero
collegheremmo due vertici di un albero ottenendo un ciclo,
facendo venire meno la condizione di aciclicità del sottografo
di ricoprimento
Visualizzazione
8
7
b
c
4
8
d
i
7
h
6
g
1
b
8
i
7
h
6
1
g
f
2
e
14
4
10
8
7
d
9
2
11
a
10
f
c
4
e
2
b
9
9
14
4
8
d
g
6
1
2
11
a
h
7
c
4
i
7
2
8
d
2
11
a
8
10
f
c
4
e
14
4
7
b
9
2
11
a
8
i
7
h
6
g
1
f
2
e
14
4
10
Visualizzazione
8
7
b
c
4
8
d
i
7
h
6
g
1
b
8
i
7
h
6
1
h
g
f
2
f
10
8
d
9
2
11
a
10
7
c
4
e
14
4
e
2
b
9
9
14
4
8
d
g
6
1
2
11
a
i
7
7
c
4
11
a
2
8
d
2
8
10
f
c
4
e
14
4
7
b
9
2
11
a
8
i
7
h
6
g
1
f
2
e
14
4
10
Visualizzazione
8
b
c
4
8
7
d
11
a
8
i
7
h
6
g
1
f
b
8
8
i
7
g
i
h
6
g
1
f
2
10
8
7
d
9
2
11
a
10
2
c
4
e
14
4
b
9
e
f
8
d
9
14
4
1
2
7
6
h
7
c
4
11
11
a
10
d
2
2
8
a
c
4
e
14
4
b
9
2
7
i
7
h
6
g
1
f
2
e
14
4
10
Visualizzazione
8
b
c
4
8
d
i
7
h
6
g
1
f
2
10
8
d
9
2
11
a
7
c
4
e
14
4
b
9
2
11
a
8
7
i
7
h
6
g
1
f
2
e
14
4
10
Analisi
• Il tempo di esecuzione per l’algoritmo di Kruskal
dipende dalla realizzazione della struttura dati per
insiemi disgiunti
• se si utilizza la realizzazione con foreste con le
euristiche:
– l’inizializzazione richiede O(V)
– il tempo necessario per ordinare gli archi è O(E lg E)
– in totale si fanno O(E) operazioni sulla foresta di insiemi
disgiunti, il che richiede un tempo O(E)
• In totale il tempo di esecuzione dell’algoritmo di
Kruskal è O(V+E lg E + E)=O(E lg E)
Algoritmo di Prim
• L’algoritmo di Prim procede mantenendo in A un
singolo albero (una singola componente connessa)
• l’albero parte da un vertice arbitrario r (la radice) e
cresce fino a quando non ricopre tutti i vertici
• ad ogni passo viene aggiunto un arco leggero che
collega un vertice in A con un vertice in V-A
• per il corollario questi archi sono sicuri per A e quindi
quando l’algoritmo termina, in A vi è un albero di
copertura minimo
• anche questo algoritmo è greedy poiché l’albero
viene esteso ad ogni passo scegliendo l’arco di peso
minimo tra quelli possibili
Algoritmo di Prim
• In questo caso A ha una unica componente connessa
che è l’intero albero di copertura che sta crescendo
• il taglio (A, V-A) rispetta A
• e quindi per il corollario qualsiasi arco leggero che
attraversa il taglio è un arco sicuro
Algoritmo di Prim
• Per avere un algoritmo efficiente si deve prestare
attenzione a come rendere facile la scelta di un
nuovo arco da aggiungere ad A
• questo viene fatto memorizzando tutti i vertici che
non sono nell’albero in costruzione in una coda con
priorità Q
• per ogni nodo la priorità è basata su un campo key[v]
che contiene il minimo tra i pesi degli archi che
collegano v ad un qualunque vertice dell’albero in
costruzione
• per ogni nodo si introduce un campo parent p[x] che
serve per poter ricostruire l’albero
Algoritmo di Prim
• L’insieme A è mantenuto implicitamente come
A={(v,p[v]) : v in V - {r} - Q}
• quando l’algoritmo termina Q è vuota e l’albero di
copertura in A è dunque:
A={(v,p[v]) : v in V - {r}}
Pseudocodice Prim
MST-Prim(G,w,r)
1 Q  V[G]
2 for ogni u in Q
3 do
key[u]  
4 key[r]  0
5 p[r]  NIL
6 while Q  
7 do
u  Extract-Min(Q)
8
for ogni v in Adj[u]
9
do
if v in Q e w(u,v)<key[v]
10
then
p[v]  u
11
key[v]  w(u,v)
Spiegazione pseudocodice
• Le linee 1-4 inizializzano la coda Q con tutti i vertici e
pongono a  l’attributo key per ogni vertice
• ad eccezione del vertice r per il quale key[r]=0 in
modo da estrarre r come elemento minimo nella fase
iniziale
• durante l'algoritmo l’insieme V-Q contiene i vertici
dell’albero che si sta costruendo
• la linea 7 identifica un vertice u incidente su di un
arco leggero che attraversa il taglio (V-Q,Q)
• si elimina u da Q e lo si aggiunge ai vertici dell’albero
Spiegazione pseudocodice
• Le linee 8-11 aggiornano i campi key e p di ogni
vertice v adiacente a u che non appartiene ancora
all’albero
• il fatto che il campo key[v] rappresenti il costo minimo
tra i pesi degli archi che collegano v ad un qualunque
vertice dell’albero in costruzione è preservato perché
se si trova un arco che collega v con l’albero (in
realtà con il vertice u corrente) che costa meno, si
aggiorna key al nuovo valore
Spiegazione dello pseudocodice
• Al ciclo successivo si esaminerà la coda Q e si
troverà che uno dei v esaminati precedentemente è
diminuito tanto da essere il vertice con chiave più
piccola
• allora si aggiungerà implicitamente v all’albero,
fissando la relazione padre-figlio migliore trovata
• e si procederà ad espandere la frontiera dei vertici
adiacenti a v, stabilendo nuove potenziali relazioni
padre-figlio
Visualizzazione
8
b
c
4
8
d
i
7
h
6
g
1
b
11
a
8
d
i
7
h
6
g
1
2
8
7
f
2
10
c
8
e
10
d
9
2
11
a
f
1
4
e
14
4
9
14
4
g
b
9
2
6
h
7
c
4
8
i
7
2
8
d
2
11
a
10
f
c
4
e
14
4
7
b
9
2
11
a
8
7
i
7
h
6
g
1
f
2
e
14
4
10
Visualizzazione
8
b
c
4
d
11
8
i
7
6
h
g
1
4
8
i
7
h
g
1
f
2
e
14
4
2
b
9
10
8
7
c
d
9
2
11
a
e
10
f
8
d
9
14
4
g
4
6
6
1
2
11
h
7
c
i
7
2
8
b
8
10
f
d
2
11
a
7
c
4
e
14
4
b
9
2
a
a
8
7
i
7
h
6
g
1
f
2
e
14
4
10
Visualizzazione
8
b
c
4
8
d
9
2
11
a
7
i
7
h
6
g
1
f
2
e
14
4
10
Analisi
• L’efficienza dell’algoritmo di Prim dipende da come
viene realizzata la coda con priorità Q
• se Q viene realizzata con uno heap binario:
– si usa Build-Heap per l’inizializzazione in tempo O(V)
– il ciclo 6 viene eseguito |V| volte ed ogni operazione ExtractMin è O(lg V)
– il ciclo for in 8 viene eseguito in tutto O(E) volte
– il controllo di appartenenza in 9 può essere eseguito in O(1)
usando un metodo di indirizzamento diretto
– l’assegnazione in 11 implica una operazione di DecreaseKey sullo heap che costa O(lg V)
• Il tempo totale è pertanto un O(V+V lg V + E lg
V)=O(E lg V) asintoticamente eguale a quello per
l’algoritmo di Kruskal