Grafi
Definizioni/1
• 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): Grafo semplice
• (vi, vj) <> (vj, vi): Grafo
diretto
ASD - Grafi
2
Esempi
• Relazioni di parentela
– Alberi genealogici
• Relazioni tra classi nei
linguaggi OO
• Grafo del Web
• Assetti societari
• Reti di trasporto
• ................
ASD - Grafi
3
Definizioni/2
• Multigrafo: E è un multinsieme
• Pseudografo: E contiene anche
coppie (vi, vi)  cappi
• Circuito in un grafo:
v1,v2,…..,vk:(vi, vi+1) ε E, v1= vk
• Ciclo in un grafo: circuito
 con
 v1
v2 ….. vk
• Grafo pesato: valore reale wk
associato ad ogni arco ek
ASD - Grafi
4
Definizioni/3
• Kn: Grafo semplice in cui
sono presenti tutti gli
archi.
n 1
n(n  1)
n

i

• Numero di archi in Kn:
2
i 1
• G’=(V’,E’) sottografo di
G=(V,E) se e solo se
V’  V ed E’  E.
• grado(v): #di archi incidenti
in v
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
ASD - Grafi
6
Rappresentazioni
• Lista di adiacenza: ogni vertice è
associato con la lista dei vertici
adiacenti.
• Lista di adiacenza 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
ASD - Grafi
7
Rappresentazioni
di grafi.
Un grafo (a)
rappresentato
con una lista
di adiacenze
(b-c),
ASD - Grafi
8
Rappresentazioni di grafi. Un grafo (a) rappresentato come una matrice
di adiacenze (d) e come una matrice d’incidenza (e)
ASD - Grafi
9
Vantaggi e Svantaggi
• Lista di adiacenza: 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: 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 ?
ASD - Grafi
10
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
– Presenza di nodi isolati
ASD - Grafi
11
Visita in profondità - DFS
• La visita procede da tutti gli
archi uscenti da un nodo.
• 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 rinumerati secondo
l’ordine di visita.
ASD - Grafi
12
Esempio di applicazione dell’algoritmo depthFirstSearch
ad un grafo
ASD - Grafi
13
L’algoritmo depthFirstSearch applicato ad un grafo orientato
ASD - Grafi
14
Implementazione della DFS/1
• I nodi sono inizialmente marcati con 0,
i=0.
• Assumi la visita sia arrivata ad un
nodo v.
• La visita prosegue da un nodo u
adiacente a v se marcato 0.
• Se nessun nodo adiacente marcato 0 è
disponibile torna al nodo da cui si è
raggiunto v oppure termina se v è il
nodo iniziale.
• Ogni volta che un nodo mai visitato è
raggiunto, questo viene marcato con i++
ASD - Grafi
15
Implementazione della DFS/2
depthFirstSearch() {
for (tutti i vertici v)
num(v)=fin(v)=0; / Vedi slide seg. */
edges = null;
i=j=1; /* Servono per aggiornare num(v)
e fin(v) */
while (<esiste un vertice v tale che
num(v) == 0>)
DFS(v);
<visualizza edges>
}
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) {
<inserisci lato (v,u) in edges>
DFS(u);
}
fin(v)=j++; /* fin(v): ultima volta che
si visita v */
}
ASD - Grafi
17
Implementazione della DFS/4
• L’implementazione iterativa
usa una pila per memorizzare
gli archi uscenti da un nodo
visitato.
• Ad ogni passo si estrae
l’arco (v,u) sulla cima della
pila.
• La visita prosegue dal nodo
adiacente u se marcato 0.
ASD - Grafi
18
Proprietà della DFS
• Gli archi che portano alla scoperta di
nuovi nodi costituiscono un albero che
copre l’intero grafo
• Questa proprietà dipende dal fatto che
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
• Gli archi che non vengono seguiti al
contrario connettono nodi con marca
superiore a nodi con marca inferiore
ASD - Grafi
19
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 controllato al più due
volte, una volta per estremo
• Complessivamente O(n + m)
ASD - Grafi
20
Visita in ampiezza - BFS
• uso di una coda per
memorizzare tutti gli archi
incidenti nel nodo visitato
• I nodi vengono marcati.
• La visita quindi procede
dall’arco (v,u) in testa alla
coda.
ASD - Grafi
21
Implementazione della BFS
breadthFirstSearch() {
for (tutti i vertici v)
num(v)=0;
edges= null;
i=1;
while (<esiste un 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);
<inserisci arco (v,u) in edges>
}
}
}
<visualizza edges>
}
ASD - Grafi
22
Un esempio di applicazione dell’algoritmo breadthFirstSearch
ad un grafo
ASD - Grafi
23
Applicazione dell’algoritmo breadthFirstSearch ad un grafo orientato
ASD - Grafi
24
Implementazione di
Grafi/Vertici
class Vertex {
String vertexName;
long vertexWeight;
public Vertex(String name, long weight)
{
vertexName = name;
vertexWeight = weight;
}
public Vertex() {
this(null, (long) 0);
}
}
ASD - Grafi
25
Esempio: generico elemento
del vettore dei vertici
/* Generico elemento del vettore dei vertici. Contiene
un vertice e la lista di adiacenza del vertice */
class adListElement {
Vertex vertex;
LinkedList adList;
public adListElement(Vertex v, LinkedList l) {
vertex = v;
adList = l;
}
public adListElement() {
this(null, null);
}
}
ASD - Grafi
26
Esempio: classe Grafo
public class Grafo {
protected static final int NO_NODES = 10;
protected adListElement vertexArray[] =
new adListElement[NO_NODES];
/* Gestisce grafi con no. nodi costante.
Se si vuole un grafo il cui
no. di nodi sia variabile occorre usare
una lista invece di un array */
/* Continua alla prossima slide */
/* Nota: questa è una classe “minima” */
ASD - Grafi
27
Esempio: classe Grafo/2
public Grafo(String inputFile) {
/* Costruisce un grafo a partire da
una sua rappresentazione su
memoria secondaria del tipo:
<String nomeNodo> <long peso>
<String primo vertice adiacente>.....\n
*/
}
/* Continua */
ASD - Grafi
28
Esempio: classe Grafo/3
public void dijkstra(String sorg,
String dest) {
/* Trova percorso minimo tra i
vertici aventi nome
sorg e dest del grafo usando
l'algoritmo di Dijkstra.
Stampa i nomi dei nodi del percorso
in successione
*/
}
/* Continua */
ASD - Grafi
29
Esempio: classe Grafo/4
public void dfs(String start) {
/* Visita in profondità il grafo
partendo dal nodo di
nome start. Stampa i nomi dei nodi
nell'ordine di
attraversamento
*/
}
} /* Fine della classe */
ASD - Grafi
30
Connettività in Grafi diretti
• 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 e da v
ad u
• Un grafo è debolmente connesso se
per ogni coppia u,v, esiste un
cammino da u a v (o viceversa)
ASD - Grafi
31
Il problema dei Cammini Minini/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,….
ASD - Grafi
32
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
• Trovare un cammino di lunghezza
minima
• Non contiene cicli per distanze
positive
ASD - Grafi
33
Single Source Shortest
Paths/1
• 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?
ASD - Grafi
34
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.
ASD - Grafi
35
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
ASD - Grafi
Nota: dist(v) indica
la distanza di v dalla
sorgente s
36
Un’esecuzione
di
DijkstraAlgorithm
ASD - Grafi
37
Dijkstra/2
DijkstraAlg(grafo_semplice_pesato, vertice source) {
for (<tutti i vertici v >)
dist(v)= ;
dist(source)=0;
R = <tutti i vertici>; Q = Ø;
while (R!=Ø) {
v = <vertice in R con minimo dist(v)>
R = R – {v}; Q = Q U {v};
for (<tutti i vertici u in R adiacenti a v>)
if (dist(u) > dist(v) + d(v,u)) {
dist(u) = dist(v) + d(v,u);
pred(u) = v;
}
}
}
ASD - Grafi
38
Dijkstra/3
• 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).
ASD - Grafi
39
Dijkstra/4
• 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.
ASD - Grafi
40
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)).
ASD - Grafi
41
Animazione disponibile a:
http://www.cs.uwa.edu.au/underg
raduate/courses/230.300/readi
ngs/graphapplet/graph.html
ASD - Grafi
42