Definizioni/1. Grafi. Esempi. Definizioni/2

(1)

Grafi

ASD - Grafi 2

Definizioni/1

• Rappresentazione di relazioni binarie

• G=(V,E), |V|=n, |E|=m

• V: insieme di Vertici

• E={(v

_i

, v

_j

): v

_i

, v

_j

_ V} : insieme di Archi

• (v

_i

, v

_j

)=(v

_j

, v

_i

): Grafo semplice

• (v

_i

, v

_j

) <> (v

_j

, v

_i

): Grafo diretto

Esempi

• Relazioni di parentela – Alberi genealogici

• Relazioni tra classi nei linguaggi OO

• Grafo del Web

• Assetti societari

• Reti di trasporto

• ...

Definizioni/2

• Multigrafo: E è un multinsieme

• Pseudografo: E contiene anche coppie (v

_i

, v

_i

)

! cappi

• Circuito in un grafo:

v

₁

,v

₂

,…..,v

_k

:(v

_i

, v

_i+1

) _ E, v

₁

= v

_k

• Ciclo in un grafo: circuito con v

₁

v

₂

….. v

_k

• Grafo pesato: valore reale w

_k

associato ad ogni arco e

_k

! !

(2)

ASD - Grafi 5

Definizioni/3

• K

_n

: Grafo semplice in cui sono presenti tutti gli archi.

• Numero di archi in K

_n

:

• G’=(V’,E’) sottografo di G=(V,E) se e solo se

V’ V ed E’ E.

• grado(v): #di archi incidenti in v

!

^"

=

"

=

"

1

1 2

) 1 (

n i

n i n n

! !

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

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:

a_ih=1 se (v_i, v_h) E, a_ih=0 altrimenti

• Matrice di Incidenza:

a_ih=1 se v_i e_h, a_ih=0 altrimenti

!

Rappresentazioni di grafi.

Un grafo (a) rappresentato con una lista di adiacenze (b-c),

(3)

ASD - Grafi 9

Rappresentazioni di grafi. Un grafo (a) rappresentato come una matrice di adiacenze (d) e come una matrice d’incidenza (e)

ASD - Grafi 10

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(n

²

)

Vantaggi: Inserimenti e cancellazioni in O(1) Svantaggi: permette di scorrere i nodi adiacenti a v in O(n)

• D.: matrice di incidenza ?

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

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.

(4)

ASD - Grafi 13

Esempio di applicazione dell’algoritmo depthFirstSearch ad un grafo

ASD - Grafi 14

L’algoritmo depthFirstSearch applicato ad un grafo orientato

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++

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);

}

(5)

ASD - Grafi 17

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) {

DFS(u);

}

fin(v)=j++; /* fin(v): ultima volta che si visita v */

}

ASD - Grafi 18

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.

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

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)

(6)

ASD - Grafi 21

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 22

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>

}

Un esempio di applicazione dell’algoritmo breadthFirstSearch

ad un grafo Applicazione dell’algoritmo breadthFirstSearch ad un grafo orientato

(7)

ASD - Grafi 25

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 26

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);

} }

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” */

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 */

(8)

ASD - Grafi 29

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 30

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 */

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)

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,….

(9)

ASD - Grafi 33

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:

v

₁

, v

₂

,….., v

_k

: (v

_i

, v

_i+1

) ! E, v

1

= s, v

_k

=t

• Lunghezza del cammino:

• Trovare un cammino di lunghezza minima

• Non contiene cicli per distanze positive ) ,

(

₁

1

1 +

!

"

= ⁱ

k

i

d v

i

v

ASD - Grafi 34

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?

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.

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 Q

5. Per ogni u adiacente a v aggiorna la distanza da s ad u attraverso nodi in Q

0 ) ( , ) ( ,

, " = ! =

#

$ v R v s dist v dist s

v pred(u)

u v d v dist u

dist

u v d v dist u

dist if

=

+

=

+

>

) , ( ) ( )

(

) , ( ) ( )

( Nota: dist(v) indica

la distanza di v dalla sorgente s

(10)

ASD - Grafi 37

Un’esecuzione di

DijkstraAlgorithm

ASD - Grafi 38

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;

} }

}

!

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).

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.

(11)

ASD - Grafi 41