Grafi
Definizioni/1
• Struttura dati per la rappresentazione di
relazioni binarie
• G=(V,E), |V|=n, |E|=m
• V: insieme di Vertici
• E={(vi, vj): vi, vj V} : insieme di Archi
• notazione
(vi, vj) =impropria
(vj, vi) = {vj, vi} Grafo semplice
• (vi, vj) ≠ (vj, vi)
Grafo diretto
giu 03
ASD - Grafi
2
Esempi
• Relazioni di parentela
– Alberi genealogici
•
•
•
•
•
Relazioni tra classi nei linguaggi OO
Grafo del Web
Assetti societari
Reti di trasporto
................
giu 03
ASD - Grafi
3
Definizioni/2
• Multigrafo: E è un multi-insieme
• Pseudografo: E contiene anche coppie (vi,
vi), dette cappi
• Cammino (di lunghezza k) in un grafo:
v1, v2,….., vk: (vi, vi+1)  E
• Circuito in un grafo: cammino con v1 = vk
• Ciclo in un grafo: circuito con vi ≠ vj
• Grafo pesato: valore reale wk associato ad
ogni arco ek
giu 03
ASD - Grafi
4
Definizioni/3
• Kn: Grafo semplice con n nodi in cui
sono presenti tutti gli archi, detto
grafo completo
– Numero di archi in Kn : n(n-1)/2
• G’ = (V’, E’) sottografo di G = (V, E) se
e solo se V’  V ed E’  E
• grado(v): #di archi incidenti in v
• (vi, vj)  E: vi adiacente a vj
giu 03
ASD - Grafi
5
Esempi di grafi: (a-d) grafi semplici; (c) un grafo completo K4;
(e) un multigrafo; (f) uno pseudografo; (g) un circuito in un grafo
orientato; (h) un ciclo nel grafo orientato
giu 03
ASD - Grafi
6
Rappresentazioni
• Liste di adiacenza: ad ogni vertice è
associata la lista dei vertici adiacenti
– può essere una tabella o una lista concatenata
• Matrice di adiacenza:
aih = 1 se (vi, vh)  E, aih = 0 altrimenti
• Matrice di incidenza:
aih = 1 se vi  eh, aih = 0 altrimenti
giu 03
ASD - Grafi
7
Rappresentazioni
di grafi.
Un grafo (a)
rappresentato
con una lista
di adiacenze
(b-c),
giu 03
ASD - Grafi
8
Rappresentazioni di grafi. Un grafo (a) rappresentato come una matrice
di adiacenze (d) e come una matrice d’incidenza (e)
giu 03
ASD - Grafi
9
Vantaggi e Svantaggi
• Lista di adiacenza: memoria O(m)
Vantaggi: permette di scorrere i nodi adiacenti
a v in O(grado(v))
Svantaggi: inserimenti e cancellazioni su liste
concatenate in O(grado(v))
• Matrice di adiacenza: memoria O(n2)
Vantaggi: Inserimenti e cancellazioni in O(1)
Svantaggi: permette di scorrere i nodi adiacenti
a v in O(n)
• D.: matrice di incidenza ?
giu 03
ASD - Grafi
10
Visita di un Grafo
•
Obiettivo: visitare una sola volta
tutti i nodi del grafo.
–
•
Difficoltà:
–
–
giu 03
Es.: visitare un porzione del grafo del
Web
Presenza di cicli: marcare i nodi visitati
Presenza di nodi isolati: la visita
termina quando sono state considerate
tutte le componenti isolate del grafo
ASD - Grafi
11
Visita in profondità - DFS
• La visita procede da ogni nodo finché tutti
gli archi adiacenti non sono stati percorsi.
• Se tutti i nodi adiacenti sono stati visitati
allora si torna al nodo “predecessore”.
• Una volta tornati al nodo di partenza si
prosegue da un nodo qualsiasi non visitato.
• I nodi vengono numerati secondo l’ordine di
visita.
giu 03
ASD - Grafi
12
Esempio di applicazione dell’algoritmo depthFirstSearch
ad un grafo
giu 03
ASD - Grafi
13
L’algoritmo depthFirstSearch applicato ad un grafo orientato
giu 03
ASD - Grafi
14
Implementazione della DFS/1
• I nodi sono inizialmente marcati con 0
• Si inizializza i=0
• Assumendo che la visita sia arrivata ad un nodo v,
essa prosegue attraverso un nodo u adiacente a v,
se marcato 0.
• Se nessun nodo adiacente marcato 0 è disponibile
si torna al nodo da cui si è raggiunto v, oppure si
termina se v è il nodo iniziale.
• Ogni volta che viene raggiunto un nodo mai visitato,
questo viene marcato con i++
• Viene marcato sia l’inizio che la fine della visita di
un nodo v, risp. num(v) e fin(v)
giu 03
ASD - Grafi
15
Implementazione della DFS/2
depthFirstSearch() {
for (tutti i vertici v)
num(v) = fin(v) = 0;
/* Vedi slide seg. */
edges = {}; // insieme vuoto
i = j = 1;
/* per aggiornare num(v) e fin(v) */
/* main loop */
while (<esiste vertice v con num(v)=0>)
DFS(v);
<visualizza edges>
}
giu 03
ASD - Grafi
16
Implementazione della DFS/3
DFS(v) {
num(v) = i++;
// num(v): prima volta che si visita v
for (<tutti i vertici u adiacenti a v>)
if (num(u) == 0) {
edges = edges  {(v, u)};
DFS(u);
}
fin(v) = j++;
// fin(v): ultima volta che si visita v
}
giu 03
ASD - Grafi
17
DFS iterativa
• L’implementazione iterativa della DFS
utilizza una pila per memorizzare gli archi
uscenti da un nodo visitato.
• Ad ogni passo si estrae l’arco (w,v) sulla
cima della pila.
• La visita prosegue su un nodo u adiacente a
v (solo se marcato 0).
• La numerazione fin(v) viene assegnata
quando si estrae un arco (w,v) con
num(w) < num(v)
giu 03
ASD - Grafi
18
DFS iterativa
void iterativeDFS(v) {
pila.push((v,v)); // arco fittizio
while(!pila.isEmpty()) {
(w,v) = pila.pop(); // arco w -> v
if (num(v) == 0) {
num(v) = i++;
edges = edges  {(w, v)};
pila.push((w,v)); // prepariamo la II marcatura
for (<tutti i vertici u adiacenti a v>)
if (num(u) == 0) pila.push((v, u));
} else if (fin(v) == 0) fin(v) = j++;//test inutile?
}
}
giu 03
ASD - Grafi
19
proprietà della DFS
• l’algoritmo DFS visita l’intera componente del
grafo raggiungibile dal nodo di partenza
• se collezioniamo gli archi (edges) che portano alla
scoperta di nuovi nodi, otteniamo una collezione di
alberi che coprono l’intero grafo
– un arco viene seguito solo se il nodo adiacente non è mai
stato raggiunto.
• gli archi seguiti connettono un nodo con marca
inferiore ad un nodo con marca superiore (forward
edges)
• gli archi che non vengono seguiti al contrario
connettono nodi con marca superiore a nodi con
marca inferiore (back edges)
giu 03
ASD - Grafi
20
Complessità della DFS
• O(n) per inizializzare marcatura dei nodi.
• Test degli archi uscenti da un nodo v:
– O(grado(v)) nella rappresentazione con lista di
adiacenza.
– O(n) nella rappresentazione con matrice di
adiacenza.
• Ogni arco viene testato al più due volte,
una volta per ogni estremo
• Complessivamente O(n + m), O(n2) (grafo
denso)
giu 03
ASD - Grafi
21
Ordinamento parziale
• Ordinamento parziale di un insieme A:
relazione d'ordine parziale (transitiva)
sugli elementi di A
– possono esistere coppie tra le quali non è
definito alcun ordine
• Un grafo diretto aciclico (DAG)
rappresenta un ordinamento parziale:
l'insieme dei vertici è l'insieme A ed esiste
un arco (u, v) sse u < v secondo l'ordine
parziale
• Se esiste un ciclo il grafo non può
rappresentare un ordine parziale: perché?
giu 03
ASD - Grafi
22
esempio
l'introduzione/eliminazione di
archi transitivi non modifica
l'ordine parziale descritto
chiusura transitiva = aggiunta
di tutti gli archi transitivi
riduzione transitiva =
eliminazione di tutti gli archi
transitivi
giu 03
ASD - Grafi
23
Applicazione ordini parziali
• Ereditarietà tra classi in linguaggi OO
• Vincoli di precedenza in progetti
complessi
• Contenimento insiemistico
• Studio di proprietà geometriche
• ...
giu 03
ASD - Grafi
24
esempio
orologio
slip
scarpe
pantaloni
calzini
giacca
camicia
cintura
cravatta
giu 03
ASD - Grafi
25
Ordinamento Topologico/1
• Un ordinamento topologico di un DAG è un
ordinamento lineare dei suoi vertici che soddisfa la
seguente condizione: per ogni arco (u, v) del grafo,
u precede v nell’ordinamento
– a ciascun vertice u si assegna un intero p(u) in modo tale
che, se esiste l'arco (u, v), allora p(u) < p(v)
– di conseguenza, se esiste un cammino da u a w, allora
p(u) < p(w): ogni nodo nell’ordine è seguito da tutti i suoi
successori
• è sempre possibile determinare un ordinamento
topologico di un DAG
giu 03
ASD - Grafi
26
Ordinamento Topologico/2
• In altre parole si vuole determinare un
ordine totale consistente con l'ordine
parziale (ce ne possono essere molti!)
• spesso si usano algoritmi che determinano
un ordinamento inverso all'ordinamento
topologico
– per semplicità, consideriamo anch'essi
"topological sorter"
• Un vertice pozzo è un vertice che non ha
archi uscenti. In un DAG esiste sempre
almeno un pozzo: perché?
giu 03
ASD - Grafi
27
Ordinamento Topologico/3
TopologicalSort() {
for(i = 1; i <= n; i++) {
<trova un vertice pozzo v>
num(v) = i;
<elimina dal DAG tutti gli
archi incidenti in v>
}
sfruttiamo la proprietà che un sottografo di
DAG è un DAG
}
un
num(·) fornisce la numerazione cercata (inversa)
giu 03
ASD - Grafi
28
Ordinamento
topologico:
g,e,b,f,d,c,a
giu 03
ASD - Grafi
29
Ordinamento Topologico/4
• In pratica un ordinamento topologico
(inverso) si ottiene se nella sequenza ogni
nodo è seguito dai suoi predecessori (e da
altri eventuali nodi)
• Si esegue una DFS e si ordinano i vertici
secondo il valore fin(v).
– il valore fin(v) è inferiore a quello dei suoi
predecessori
• L’ordinamento topologico si ottiene dalla
sequenza ordinata secondo fin(v) scandita
in ordine inverso. Come si dimostra?
giu 03
ASD - Grafi
30
Ordinamento Topologico/5
TS(v)
num(v) = i++;
for(<tutti i vertici u adiacenti a v>)
if (num(u) == 0)
TS(u);
else if (fin(u) == 0)
errore; // identificato un ciclo
/* siamo tornati ad u visitando i successori
di u */
/* dopo avere esaminato tutti i predecessori,
assegna a v un numero maggiore di quelli
assegnati a qualsiasi predecessore */
fin(v) = j++;
giu 03
ASD - Grafi
31
Ordinamento Topologico/6
topologicalSorting(digraph)
for(<tutti i vertici v>)
num(v) = fin(v) = 0;
i = j = 1;
while (<esiste v tale che num(v) == 0>)
TS(v);
<Visualizza i vertici in ordine inverso secondo
fin(v)>
/* conviene "organizzarsi" in anticipo per non
dover pagare il costo di un ordinamento */
giu 03
ASD - Grafi
32
Connettività in Grafi diretti
• Due nodi u,v sono connessi in un grafo
orientato se esiste un cammino diretto che
collega u a v.
• Un grafo diretto è fortemente connesso se
per ogni coppia u,v, esiste un cammino da u
a v.
• Un grafo è debolmente connesso se ogni
coppia di nodi è connessa da un cammino
quando gli archi orientati si sostituiscono
con archi non orientati.
giu 03
ASD - Grafi
33
Componenti fortemente connesse SCC/1
• Un grafo diretto può essere decomposto in
componenti fortemente connesse, V1 , V2 ,…
, Vk, tale che
–
–
–
–
V = V1  V2  ...  Vk
 u, v  Vj: u connesso a v, v connesso ad u
Vj è un insieme massimale
Vi  Vj = Ø
• GT = (V, ET): (u, v)  E  (v, u)  ET
giu 03
ASD - Grafi
34
SCC / 2
StronglyConnectedComponent(G)
Esegui DFS(G) per calcolare fin(v) per
ogni vertice v;
Calcola GT;
Calcola DFS(GT) considerando i nodi nel
"main loop" in ordine decrescente
secondo fin(v);
Output ogni albero di DFS(GT) come una
componente fortemente connessa separata
giu 03
ASD - Grafi
35
G
GT
a
b
c
d
a
b
c
d
8/6
6/8
1/5
5/4
2
1
4
5
h
e
f
4/2
3
7
e
7/7
f
g
3/1
2/3
num/fin
g
h
6
8
num
Radici Alberi DFS: b, c, g, h
SCC: {a,b,e} {c,d} {f,g} {h}
Esempio di esecuzione dell’algoritmo per SCC
giu 03
ASD - Grafi
36
Visita in ampiezza - BFS
• La visita in ampiezza fa uso di una
coda per memorizzare tutti gli archi
incidenti nel nodo v visitato che
portano ad un nodo marcato 0.
• I nodi raggiungibili non marcati
vengono quindi marcati.
• La visita procede dall’arco (v,u) in
testa alla coda.
giu 03
ASD - Grafi
37
Implementazione della BFS
breadthFirstSearch() {
for (tutti i vertici v)
num(v) = 0;
edges = {}; // empty set
i = 1;
while (<esiste vertice v tale che num(v) == 0>) {
num(v) = i++;
enqueue(v);
while (<la coda non è vuota>) {
v = dequeue();
for (<tutti i vertici u adiacenti a v>)
if (num(u) == 0) {
num(u) = i++;
enqueue(u);
edges = edges  {(v, u)}
}
}
}
<visualizza edges>
}
giu 03
ASD - Grafi
38
Un esempio di applicazione dell’algoritmo breadthFirstSearch
ad un grafo
giu 03
ASD - Grafi
39
Applicazione dell’algoritmo breadthFirstSearch ad un grafo orientato
giu 03
ASD - Grafi
40
Il Problema dei Cammini Minimi
• G=(V,E) è un grafo pesato sugli archi
• d(u,v), (u,v) E: peso sull’arco (u,v)
• Cammino dal nodo s al nodo t:
v1, v2,….., vk: (vi, vi+1) E, v1= s, vk=t
k 1
• Lunghezza del cammino:  d (vi , vi 1 )
i 1
• Il cammino di lunghezza minima non
contiene cicli ……se le distanze sugli archi
sono positive. Come si dimostra?
giu 03
ASD - Grafi
41
Il problema dei Cammini Minimi/2
• Determinare il cammino di lunghezza
minima
– dal nodo s al nodo t
– dal nodo s a tutti gli altri nodi V (SSSP)
– tra tutte le coppie di nodi del grafo (APSP)
• Numerose applicazioni: reti stradali, reti di
comunicazione, scheduling di progetti,
progetto di circuiti,….
giu 03
ASD - Grafi
42
Single Source Shortest
Paths/1
• Consideriamo un grafo pesato con pesi non
negativi.
• Determinare il cammino minimo da un nodo
s a tutti i nodi V del grafo
• Ogni sottocammino di un cammino minimo è
esso stesso un cammino minimo.
• Ex: s,…,i,…j,…,v: cammino minimo da s a v
i,…,j è un cammino minimo da i a j.
Come si dimostra?
giu 03
ASD - Grafi
43
Single Source Shortest
Paths/2
• La collezione dei cammini minimi da s a tutti i nodi
V forma un albero. Come si dimostra?
• Algoritmi per SSSP mantengono ad ogni istante
delle etichette sui nodi.
• Etichette rappresentano delle approssimazioni
delle distanze dalla sorgente.
• Vi sono algoritmi che ad ogni passo fissano alcune
etichette ai loro valori finali, ex Dijkstra.
• Altri algoritmi, ex: Bellmann & Ford, possono
modificare tutte le etichette lungo l’intera
esecuzione dell’algoritmo.
giu 03
ASD - Grafi
44
Dijkstra/1
1. Due insiemi di nodi Q ed R.
2. Inizialmente Q= {}, R={1,..,n}
3. v  R, v  s, dist (v)  , dist ( s )  0
4. Ad ogni passo estrai il nodo v in R con min dist(v)
ed inserisci v in Q
5. Per ogni u adiacente a v aggiorna la distanza da s
ad u attraverso nodi in Q:
if dist (u )  dist (v )  d (v, u )
dist (u )  dist (v )  d (v, u )
pred(u)  v
giu 03
ASD - Grafi
45
Un’esecuzione
di
DijkstraAlgorithm
giu 03
ASD - Grafi
46
Dijkstra/2
• Ad ogni passo si determina la distanza minima di un
nodo v in R. Il nodo viene inserito in Q.
• Dijkstra termina in n passi.
• Ad ogni passo occorre determinare il nodo v in R
con minimo valore dist(v), O(log n) usando un heap
per la coda di priorità.
• Occorre poi eseguire il rilassamento per ogni
adiacente u di v, O(grado(u)) vertici, ed
eventualmente aggiornare la priorità.
Complessivamente O(m log n)
• Complessità di Dikstra O((n + m )log n).
giu 03
ASD - Grafi
47
Dijkstra/3
• Correttezza: Dimostrare che dist(v) è la distanza
minima d(v) da v ad s quando v è incluso in Q.
• Per assurdo, considera il primo nodo inserito in Q
per cui d (v)  dist (v)
• Esiste un cammino alternativo più breve che
contiene almeno un nodo in R.
• Sia v’ l’ultimo nodo in R sul cammino da v a s.
• v’ è connesso ad s con un cammino formato di soli
nodi in Q con dist(v’)<dist(v).
• Una contraddizione poiché v’ sarebbe stato
selezionato in luogo di v.
giu 03
ASD - Grafi
48
Dijkstra/4
DijkstraAlg(grafo digraph, vertice source)
for tutti i vertici v
dist(v)= ;
dist(source)=0;
R = tutti i vertici;
while R!=0
v = vertice in R con minimo dist(v);
for tutti i vertici u in R adiacenti a v
if dist(u)>dist(u)+d(v,u)
dist(u)= dist(u)+d(v,u;
pred(u) = v;
giu 03
ASD - Grafi
49
Dijkstra/5
• La collezione dei pred(u) forma
l’albero dei cammini minimi con
sorgente s.
• Si può risolvere il problema APSP
eseguento n volte Dijkstra a partire
da n sorgenti. Complessità:O(nlog n(m
+n)).
giu 03
ASD - Grafi
50
Minimo Albero Ricoprente –
MST
• Si desidera selezionare un sottografo di un
grafo che mantenga la connettività tra
tutti i nodi al minore costo possibile.
• Ex: selezionare un sottoinsieme di tratte
aeree che permettono di raggiungere tutte
le destinazioni con costo minimo.
• Assumiamo un grafo semplice e pesi non
negativi d(u,v) sugli archi.
• La rete ottima è un albero. Perché?
giu 03
ASD - Grafi
51
8
b
11
8
h
4
i
7
d
9
2
4
a
c
7
14
e
6
1
g
2
f
10
Il Minimum Spanning Tree di un
Grafo
giu 03
ASD - Grafi
52
MST / 2
• Strategie Greedy: procedi attraverso una
sequenza di scelte ottime locali.
• Strategie greedy convergono alla soluzione
ottima solo in casi particolari.
• Per il MST, consideriamo algoritmi che
mantengono la seguente proprietà:
P1. Ad ogni passo l’insieme degli archi
selezionati è un sottoinsieme del MST
finale.
• Ad ogni passo un nuovo arco viene aggiunto
alla soluzione mantenendo P1
giu 03
ASD - Grafi
53
MST / 3
• Definiamo un arco “safe” se può essere
aggiunto ad un MST mantenendo P1
• Il generico algoritmo Greedy:
Algorithm_MST(G,d)
A={}
while A non è uno Spanning Tree
trova un arco (u,v) safe per A;/* Safe
Inserisci (u,v) in A;
return A
• Diversi algoritmi differiscono per la
strategia di ricerca di un arco safe.
• Questo algoritmo ha n-1 iterazioni
giu 03
ASD - Grafi
54
Archi “safe”
• Una partizione S, V/S dei vertici
rispetta un insieme di archi A se
(u, v)  A  u, v  S , oppure u,v V / S
• L’arco (u,v) di peso minimo che
attraversa il taglio S, cioè u  S , v  V / S
è safe per A
• Si dimostra che esiste un MST che
include sia A che (u,v)
giu 03
ASD - Grafi
55
Prova
• Per assurdo, assumi che un MST T’
include A ma non include (u,v).
• Considera il taglio (S, V/S) per cui
(u,v) è safe. Vi è un arco in T’ che
attraversa il taglio (S, V/S).

• (u,v) forma un ciclo in T’ con (x,y).
• Poiché d(u,v)<=d(x,y) T = T’ /(x,y) 
(u,v) ha costo minore.
giu 03
ASD - Grafi
56
Algoritmo di Boruvka
• L’insieme A forma un insieme di componenti
connesse
• Safe: Determina l’arco di costo minimo che
connette due componenti connesse in A.
• I pesi degli archi vengono memorizzati in
una coda di priorità.
• Ad ogni passo si estrae il minimo e si
eliminano anche tutti gli archi tra due
componenti che vengono unite.
• Complessità: O(m log n). m eliminazioni da
giu 03
ASD - Grafi
57
un heap.
8
b
11
8
6
1
h
b
a
4
i
7
7
c
h
giu 03
6
g
2
Esecuzione
dell’Algoritmo
di Boruvka
e
10
f
d
9
5
i
1
14
2
g
3
4
d
9
2
4
a
7
c
e
La numerazione indica
l’ordine di selezione
degli archi del MST
f
ASD - Grafi
58
Algoritmo di Kruskal
• Ordina gli archi secondo peso crescente
• Safe: Determina l’arco di peso minimo che
non induce cicli in A.
• Complessità:
– Ordinamento degli archi in O(m log m).
– Verifica m volte se si ha un ciclo. Determinare
l’esistenza di un ciclo può essere svolto in O(log
n) utilizzando una struttura dati per insiemi
disgiunti
• L’esecuzione sull’esempio è identica
all’algoritmo di Boruvska
giu 03
ASD - Grafi
59
Gestione di insiemi/1
• Ogni insieme ha uno dei suoi elementi come
rappresentante.
• L’elemento rappresentante non viene modificato
finchè l’insieme non viene modificato.
• Operazioni:
– Make-Set(x): costruisce insieme di un elemento con
rappresentante l’elemento stesso
– Union(x,y): unisce due insiemi con rappresentanti x ed y.
– Find-Set(x): restituisce il rappresentante dell’insieme
contenente x.
giu 03
ASD - Grafi
60
Gestione di Insiemi/2
• Sequenza di m operazioni su elementi
implementabili in tempo O(m+n log n) con foreste
di insiemi disgiunti.
• Ogni elemento è un nodo di un albero.
• Ogni insieme è un albero distinto il cui
rappresentante è il nodo alla radice.
• Make-Set(x): nuovo albero con nodo.
• Find-Set(x): risali l’albero contente x fino alla
radice.
• Union(x,y): albero con minor numero di nodi viene
appeso alla radice dell’altro. Union-by-weight.
giu 03
ASD - Grafi
61
Algoritmo di Kruskal
MST-Kruskal(G,w)
A=0;
v V , Make-Set(v);
Ordina E in ordine non decrescente;
Per ogni (u, v)  E secondo l’ordine
If Find-Set(u)<>Find-Set(v)
then A=A  {(u,v)};
Union(u,v};
Return A
giu 03
ASD - Grafi
62
Algoritmo di Prim / 1
• L’insieme A forma ad ogni passo una
singola componente connessa
• Inizialmente A contiene {u,v} tale che
(u,v) è l’arco di costo minimo.
• Ad ogni passo si inserisce in A l’arco
di costo minimo che attraversa il
taglio A, V/A.
giu 03
ASD - Grafi
63
Algoritmo di Prim /2
• L’implementazione di Prim è simile a
Dijkstra con Q=A. Un Heap R memorizza il
peso minimo di un arco che connette un
nodo di R ad un nodo di A.
• Ad ogni passo un nodo v di minima priorità è
inserito in A (e rimosso dall’Heap R)
• Per tutti i nodi u in R adiacenti a v si
aggiorna la priorità di u se d(v,u) è minore
della priorità corrente di u.
• Complessità: O(m log n) per l’aggiornamento
della priorià che può essere svolta m volte.
giu 03
ASD - Grafi
64
Algoritmo di Prim / 3
PrimAlg(grafo graph, vertice s)
A = {s};
R = tutti i vertici/s;
for tutti i vertici v
rank(v)=min{d(s,v),  };
while R!=0
estrai vertice v in R con minimo rank(v)=d(r,v),r  A ;
A = A  v;
pred(v) = r;
for tutti i vertici u in R adicacenti ad v
if rank(u)>d(v,u)
rank(u) = d(v,u);
giu 03
ASD - Grafi
65
8
b
a
11
h
b
6
1
g
6
c
4
7
h
giu 03
2
14
f
5
g
2
Esecuzione
dell’Algoritmo
di Prim
e
10
d
8
3
i
1
d
4
i
7
7
9
2
4
8
a
c
e
La numerazione indica
l’ordine di selezione
degli archi del MST
f
ASD - Grafi
66
Esempio di compito d’Esame
1.
2.
3.
4.
5.
giu 03
Indicare un esempio di caso peggiore per
l’algoritmo di Quicksort.
Scrivere un metodo per il calcolo del
predecessore in un albero binario di ricerca.
Risolvere la seguente ricorrenza: T(n)=3T(n/2)+n
Mostrare l’inserimento di un elemento in un dato
albero AVL.
Illustrare l’esecuzione dell’algoritmo per
l’ordinamento topologico su un dato ordine
parziale.
ASD - Grafi
67