Proprietà Osservative delle Binarie X Contenenti Stelle di Neutroni
Grafi. giu 03ASD - Grafi2 Definizioni/1 Struttura dati per la rappresentazione di relazioni binarie...
-
Upload
prudenzio-tedesco -
Category
Documents
-
view
216 -
download
0
Transcript of Grafi. giu 03ASD - Grafi2 Definizioni/1 Struttura dati per la rappresentazione di relazioni binarie...
Grafi
giu 03 ASD - Grafi 2
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
• (vi, vj) = (vj, vi) = {vj, vi} Grafo semplice
• (vi, vj) ≠ (vj, vi) Grafo diretto
notazione impropria
giu 03 ASD - Grafi 3
Esempi
• Relazioni di parentela – Alberi genealogici
• Relazioni tra classi nei linguaggi OO• Grafo del Web• Assetti societari• Reti di trasporto• ................
giu 03 ASD - Grafi 4
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 5
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 6
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 7
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 8
Rappresentazioni di grafi. Un grafo (a) rappresentato con una lista di adiacenze (b-c),
giu 03 ASD - Grafi 9
Rappresentazioni di grafi. Un grafo (a) rappresentato come una matrice di adiacenze (d) e come una matrice d’incidenza (e)
giu 03 ASD - Grafi 10
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 11
Visita di un Grafo
• Obiettivo: visitare una sola volta tutti i nodi del grafo.
– Es.: visitare un porzione del grafo del Web
• Difficoltà: – Presenza di cicli: marcare i nodi visitati – Presenza di nodi isolati: la visita
termina quando sono state considerate tutte le componenti isolate del grafo
giu 03 ASD - Grafi 12
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 13
Esempio di applicazione dell’algoritmo depthFirstSearch ad un grafo
giu 03 ASD - Grafi 14
L’algoritmo depthFirstSearch applicato ad un grafo orientato
giu 03 ASD - Grafi 15
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 16
Implementazione della DFS/2depthFirstSearch() {for (tutti i vertici v)
num(v) = fin(v) = 0; /* Vedi slide seg. */edges = {}; // insieme vuotoi = 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 17
Implementazione della DFS/3DFS(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 18
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 19
DFS iterativavoid iterativeDFS(v) {pila.push((v,v)); // arco fittiziowhile(!pila.isEmpty()) {(w,v) = pila.pop(); // arco w -> vif (num(v) == 0) {num(v) = i++;edges = edges {(w, v)};pila.push((w,v)); // prepariamo la II marcaturafor (<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 20
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 21
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 22
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 23
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 24
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 25
esempioslip
calzini
camicia cintura
orologio
giacca
pantaloni
cravatta
scarpe
giu 03 ASD - Grafi 26
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 27
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 28
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 un DAG è un DAGnum(·) fornisce la numerazione cercata (inversa)
giu 03 ASD - Grafi 29
Ordinamento topologico:
g,e,b,f,d,c,a
giu 03 ASD - Grafi 30
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 31
Ordinamento Topologico/5TS(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 32
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 33
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 34
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 35
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 36
Esempio di esecuzione dell’algoritmo per SCC
num/fin
5/4
G
1/5
c
6/8
d
8/6
a b
4/22/3
g
3/1
h
7/7
e f
5
GT
4
c
1
d
2
a b
86
g
7
h
3
e f
SCC: {a,b,e} {c,d} {f,g} {h}
num
Radici Alberi DFS: b, c, g, h
giu 03 ASD - Grafi 37
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 38
Implementazione della BFSbreadthFirstSearch() {
for (tutti i vertici v)num(v) = 0;
edges = {}; // empty seti = 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 39
Un esempio di applicazione dell’algoritmo breadthFirstSearch ad un grafo
giu 03 ASD - Grafi 40
Applicazione dell’algoritmo breadthFirstSearch ad un grafo orientato
giu 03 ASD - Grafi 41
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
• Lunghezza del cammino:• Il cammino di lunghezza minima non
contiene cicli ……se le distanze sugli archi sono positive. Come si dimostra?
),( 1
1
1
i
k
ii vvd
giu 03 ASD - Grafi 42
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 43
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 44
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 45
Dijkstra/1
1. Due insiemi di nodi Q ed R. 2. Inizialmente Q= {}, R={1,..,n}3. 4. Ad ogni passo estrai il nodo v in R con min
dist(v) ed inserisci v in Q5. Per ogni u adiacente a v aggiorna la distanza
da s ad u attraverso nodi in Q:
0)(,)(,, sdistvdistsvRv
vpred(u)
uvdvdistudist
uvdvdistudistif
),()()(
),()()(
giu 03 ASD - Grafi 46
Un’esecuzione diDijkstraAlgorithm
giu 03 ASD - Grafi 47
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 48
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• 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.
)()( vdistvd
giu 03 ASD - Grafi 49
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 50
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 51
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 52
a
b
h
c d
g
e
f
i
8 7
9
1021
8
4
11 144
2
67
Il Minimum Spanning Tree di un Grafo
giu 03 ASD - Grafi 53
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 54
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 Treetrova un arco (u,v) safe per A;/* SafeInserisci (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 55
Archi “safe”
• Una partizione S, V/S dei vertici rispetta un insieme di archi A se
• L’arco (u,v) di peso minimo che attraversa il taglio S, cioèè safe per A
• Si dimostra che esiste un MST che include sia A che (u,v)
SVvSu /,
SV u,vSvuAvu /,,),( oppure
giu 03 ASD - Grafi 56
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 57
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 un heap.
giu 03 ASD - Grafi 58
a
b
h
c d
g
e
f
i
8 7
9
1021
8
4
11 1442
67
a
b
h
c d
g
e
f
i
1 2
34
6
5
7
9
Esecuzione dell’Algoritmo
di Boruvka
La numerazione indica l’ordine di selezione degli archi del MST
giu 03 ASD - Grafi 59
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 60
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 61
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 62
Algoritmo di Kruskal
MST-Kruskal(G,w)
A=0;
Ordina E in ordine non decrescente;
Per ogni secondo l’ordine
If Find-Set(u)<>Find-Set(v)
then A=A {(u,v)};
Union(u,v};
Return A
Set(v);-Make ,Vv
Evu ),(
giu 03 ASD - Grafi 63
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 64
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 65
Algoritmo di Prim / 3PrimAlg(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), ; 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);
Ar
giu 03 ASD - Grafi 66
a
b
h
c d
g
e
f
i
8 7
9
1021
8
4
11 1442
67
a
b
h
c d
g
e
f
i
1 2
47
5
3
6
8
Esecuzione dell’Algoritmo
di Prim
La numerazione indica l’ordine di selezione degli archi del MST
giu 03 ASD - Grafi 67
Esempio di compito d’Esame
1. Indicare un esempio di caso peggiore per l’algoritmo di Quicksort.
2. Scrivere un metodo per il calcolo del predecessore in un albero binario di ricerca.
3. Risolvere la seguente ricorrenza: T(n)=3T(n/2)+n
4. Mostrare l’inserimento di un elemento in un dato albero AVL.
5. Illustrare l’esecuzione dell’algoritmo per l’ordinamento topologico su un dato ordine parziale.