Grafo direttoUniversità degli Studi di Milano

Marco Frasca

Un grafo diretto G è una coppia ordinata (V, E), dove

V è l’insieme dei vertici {1,2,3,…,n} (anche detti nodi).E ⊆ V × V è un insieme di coppie ordinate (u,v) dette archi diretti

3

2

5

6

1

4

7

V= {1,2,3,4,5,6,7}

E= {(1, 2), (1, 3), (2, 3), (4, 3), (5, 4), (5, 6),

(6, 1), (6, 2), (6, 5), (7, 7)}

Grafo non direttoUniversità degli Studi di Milano

Marco Frasca

Un grafo non diretto G è una coppia (V, E), dove ● V è l’insieme dei vertici {1,2,3,…,n} (anche detti nodi).● E è un insieme di coppie non ordinate di elementi di V

➢ Coppia non ordinata {x, y}, con x, y ∈ V e x ≠ y, detta arco non diretto

Nota: (u,v) risulta identico a (v,u)! Per rappresentare il grafo G con un grafo diretto, basta sostituire ogni arco non diretto {u,v} con i due archi diretti (u,v) e (v,u).

3

2

5

6

1

4

V= {1,2,3,4,5,6,7}

7

Incidenza e adiacenzaUniversità degli Studi di Milano

Marco Frasca

• Nel grafo diretto G = (V,E), si dice che l’arco diretto (u,v) è incidente da u in v, ossia l’arco esce da u ed entra in v.

• Nel grafo non diretto G=(V,E), si dice semplicemente che l’arco non diretto (u,v) è incidente su u e v.

• I vertici u e v risultano adiacenti tra di loro.

• In un grafo diretto G si può scrivere u → v, per mettere in evidenza il verso di percorrenza dei due vertici adia-centi.

vu vu

Grado di un nodoUniversità degli Studi di Milano

Marco Frasca

• Il grado di un nodo u corrisponde al numero di archi in-cidenti su u.• In un grafo diretto si può anche calcolare il grado uscen-te o il grado entrante di u, rispettivamente il numero di ar-chi uscenti da u o entranti in u.

uu

d(u)=5d

+(u)=2

d-(u)=3

Cammini in un grafoUniversità degli Studi di Milano

Marco Frasca

• Un cammino è una sequenza <v1, v2, …,vk> di nodi a due a due adiacenti, dove (vi, vi+1) con i = 1,…,k-1 è un arco del grafo.

• Se v1 = u e vk = v , allora si dice che esiste un cam-mino tra u e v (u~>v) e che v è raggiungibile da u.

• Il cammino si dice semplice se i vertici sono tutti distinti.

• Un sottocammino <vi, vi+1, …,vj> (0≤ i ≤ j ≤k) è una sottosequenza continua dei vertici che compongono un cammino.

Cicli in un grafoUniversità degli Studi di Milano

Marco Frasca

• Un ciclo è un cammino <v1, v2, …,vk> dove v1=vk.

• Quando il sottocammino <v1, v2, …,vk-1> del ciclo è semplice allora di dice che il ciclo è semplice.

• Un grafo senza cicli è detto aciclico.

5

6

3

21

Grafo connessoUniversità degli Studi di Milano

Marco Frasca

• Un grafo non diretto è connesso se ogni coppia di ver-tici è connessa da un cammino.

• Un grafo diretto è detto fortemente connesso se esi-ste un cammino tra ogni coppia di vertici. Quindi si ha u~>v e v~>u per ogni coppia di vertici (u,v).

3

2

5

6

1

4

7

3

2

5

6

1

4

7

G1 non connesso G2 connesso

SottografiUniversità degli Studi di Milano

Marco Frasca

• Un grafo G’’= (V’’, E’’) è un sottografo di un grafo G = (V, E) (diretto o non diretto), se si ha V’’ V e E’’ E.

• Un sottografo di G viene detto indotto da V’’ quando l’insieme degli archi è definito da tutti gli archi di G aventi come vertici incidenti solo quelli appartenenti al sottoinsieme V’’. Ossia:

E’’={(u,v) ∊ E: u, v ∊ V’’}

3

2

5

6

1

4

7

G1

3

21

4

G2 sottografo di G1

3

21

4

G3 sottografo indotto da V’’={1,2,3,4}

Tipi di GrafiUniversità degli Studi di Milano

Marco Frasca

• Una foresta è un grafo aciclico.• Un albero è un grafo aciclico connesso.

2

34

1

6 87 9105

34

6 87 9105

Tipi di GrafiUniversità degli Studi di Milano

Marco Frasca

• Un grafo non diretto è detto completo quando ogni coppia di vertici ha un arco che li unisce.

• Un grafo è un bipartito quando l’insieme dei vertici V può es-sere partizionato in due insieme V’ e V’ tali per cui ogni arco di G è formato da un vertice di V’ e uno di V’’.

2

34

1 4

1

6

3 5

2

G1 grafo completo G2 grafo bipartito

'','chetale),( VvVuEvu

V’

V’’

Rappresentazioni di un Grafo Università degli Studi di Milano

Marco Frasca

● Liste di adiacenza: ad ogni vertice è associata la lista dei vertici adiacenti– può essere una vettore o una lista concatenata (se il grafo

è dinamico)

● Matrice di adiacenza: matrice A nxn dove∀ i, h ∈{1,..., n}aih = 1 se (vi, vh) Eaih = 0 altrimenti

Rappresentazioni di un Grafo Università degli Studi di Milano

Marco Frasca

a b c d e f ga 0 0 1 1 0 1 0

b 0 0 0 1 1 0 0

c 1 0 0 0 0 1 0

d 1 1 0 0 1 1 0

e 0 1 0 1 0 0 0

f 1 0 1 1 0 0 0

g 0 0 0 0 0 0 0

Rappresentazione con matrice di adiacenza

Quale rappresentazione?Università degli Studi di Milano

Marco Frasca

● Lista di adiacenza: memoria O(m), m = |E|<= n2

Vantaggi: permette di scorrere i nodi adiacenti a v in O(grado(v))

Svantaggi: inserimenti e cancellazioni su liste con-catenate 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)

Visita di un GrafoUniversità degli Studi di Milano

Marco Frasca

• Operazione che consiste nel visitare una sola volta tutti i nodi del grafo – Es.: visitare un sottografo 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

Visita in profondità: Depth First Search (DFS) Università degli Studi di Milano

Marco Frasca

● Dato un grafo G=(V,E), la visita in profondità (in inglese depth-first search) esplora il grafo andando ogni volta il più possibile in profondità, partendo da un qualsiasi nodo.

• Per ogni vertice v in cui la visita giunge, si prosegue la visita sugli archi non ancora esplorati.

• Se sul vertice v in visita si sono esplorati tutti gli archi, la visita di v si dice “terminata” e si torna al vertice di “padre”

• Se sul grafo rimane qualche vertice non scoperto si ricomincia la visita in profondità su uno di quei vertici.

● L’intero processo è ripetuto finché non vengono visitati tutti i vertici del grafo.

Visita in profondità: Depth First Search (DFS) Università degli Studi di Milano

Marco Frasca

Strutture dati utilizzate:

• Liste di adiacenza Adj: per conoscere i vertici adiacenti a un ver-tice.

• color[u]: si colora il vertice u di bianco (vertice non scoperto), di grigio (vertice appena scoperto) e di nero (ha finito di visitare tutta la sua lista di Adiacenza).

• p[u]: il predecessore di u nella foresta DFS.

• d[u]: tempo in cui viene scoperto u.

• f[u]: tempo in cui viene finita la visita in u. Si ha d[u]<f[u].

Nota: u è bianco (WHITE) prima di d[u], grigio (GRAY) tra d[u] e f[u], infine nero (BLACK) dopo f[u].

Visita in profondità: Depth First Search (DFS)

DFS(G)1. for ogni vertice u in V[G] // inizializzazione di ogni vertice2. do color[u] ← WHITE3. p[u] ← NIL4.time ← 05. for ogni vertice u in V[G] 6. do if color[u] = WHITE7. then DFS-VISIT(u) // visita da ogni vertice non

ancora scoperto

Università degli Studi di Milano

Marco Frasca

Visita in profondità: Depth First Search (DFS)

DFS-VISIT(u)1. color[u] ← GRAY // vertice diventa grigio, appena scoperto 2. d[u] ← time // tempo inizio visita lista adiacenza3. time ← time + 14. // Qui operazioni sul nodo5. for ogni vertice v in Adj[u] 6. do if color[v] = WHITE7. then p[v] ← u8. DFS-VISIT(v) // visita subito vertice non

ancora scoperto9. color[u] ← BLACK // vertice diventa nero, ha visitato

tutta l’adiacenza10. f[u] ← time // tempo fine visita lista adiacenza11. time ← time + 1

Università degli Studi di Milano

Marco Frasca

EsempioUniversità degli Studi di Milano

Marco Frasca

v

y

w

z

1/

u

x

(a)

v

y

w

z

1/

u

x

(b)2/

v

y

w

z

1/

u

x

(c)2/

3/

v

y

w

z

1/

u

x

(d)

v

y

w

z

1/

u

x

(e)2/

v

y

w

z

1/

u

x

(f)2/

3/

2/

3/4/ 3/4/ 4/5

v

y

w

z

1/

u

x

(g)2/

3/64/5

v

y

w

z

1/

u

x

(h)2/7

3/64/5

v wu v wu

v wu v wuv wu v wuv wu v wu

v wu v wu v wu v wu

y zx y zx

y zxy zxy zx

EsempioUniversità degli Studi di Milano

Marco Frasca

v

y

w

z

1/8

u

x

(l)2/7

3/64/5

v

y

w

z

1/8

u

x

(m)2/7

3/64/5

9/

v

y

w

z

1/8

u

x

(o)2/7

3/64/5

9/

10/

v

y

w

z

1/8

u

x

(p)2/7

3/64/5

9/

10/

v

y

w

z

1/8

u

x

(q)2/7

3/64/5

9/

10/11

v

y

w

z

1/8

u

x

(r)2/7

3/64/5

9/12

10/11

Complessità

Analisi del tempo di esecuzione:

● Ci sono due cicli in DFS() che vengono eseguiti Θ(|V|) volte.

● DFS-VISIT(u) viene eseguito esattamente una volta per ogni vertice in V.

● Durante l’esecuzione di DFS-VISIT(u) il ciclo nelle linee 5-8 viene eseguito |Adj[u]| volte. Poiché la somma di tutte le liste di adiacenza è Θ(|E|), si ha che il costo totale del ciclo in DFS-VISIT() è Θ(|E|).

● Quindi, il tempo totale di esecuzione è Θ(|V| + |E|).

Università degli Studi di Milano

Marco Frasca

Proprietà

1. Il vettore p contiene tutte le componenti connesse del grafo.

Se il grafo è diretto, l'algoritmo in p vengono individuate le componenti fortemente connesse.

2. Teorema delle parentesi

In ogni visita in profondità di un grafo G=(V,E), per ogni coppia di nodi u, v in V, con A=[d[u], f[u]] e B=[d[v], f[v]]. Allora una e una sola delle seguenti condizioni è vera:

1.

2. e u è discendente di v in un albero DFS.

3. e v è discendente di u in un albero DFS.

Università degli Studi di Milano

Marco Frasca

BA

BA

AB

Visita in ampiezza: Breath First Search (BFS)

● Dato un grafo G = (V, E) e uno specifico vertice s chiamato sorgente, la visita in ampiezza esplora gli archi di G per scoprire ogni vertice che sia raggiungibile a partire da s.

● Essa calcola anche, per ogni vertice raggiungibile da s, la distanza minima (in numero di archi) da s.

● Inoltre, produce un “albero BFS” che ha come radice s e ne comprende tutti vertici raggiungibili. Nell’albero BFS il cammino da s a v corrisponde ad un “cammino minimo”, quando gli archi sono non pesati.

● L’algoritmo funziona per grafi orientati e non orientati.

Università degli Studi di Milano

Marco Frasca

Visita in ampiezza: Breath First Search (BFS)

● La visita in ampiezza esplora i nodi del grafo a partire da quelli a distanza 1 da s. Dopo aver visitato i nodi a distanza 1, visita quelli a distanza 2. E così via.

● Strutture dati utilizzate:● Liste di adiacenza Adj: per conoscere i vertici adiacenti a un

vertice.● color[u]: per colora il vertice u di bianco (vertice non scoperto), di

grigio (vertice appena scoperto) e di nero (vertice di cui ho scoperto tutti i vicini).

● d[u]: la distanza di u da s. All’inizio è ∞.

● p[u]: il predecessore di u nell’albero BFS.

● Q: coda FIFO (First in , first out)

Università degli Studi di Milano

Marco Frasca

BFS

BFS(G,s)1. for ogni vertice u in V[G] / {s} // inizializzazione di ogni vertice2. do color[u] ← WHITE3. d[u] ← ∞; p[u] ← NIL4. colors[s] ← GRAY // si comincia dal vertice s5. d[s] ← 0; p[s] ← NIL6. Q ← {s} // Q= coda dei vertici grigi 7. // qui operazioni su s 8. while Q ≠Ø // termina quando la coda è vuota9. do u ← head[Q] // prendi prossimo elemento dalla coda10. for ogni vertice v in Adj[u] // scopri vertici bianchi adiacenti11. do if color[v] = WHITE12. then color[v] ← GRAY // diventano grigi13. d[v] ← d[u] + 1; p[v] ← u // la distanza è d[u] +1. Il predecessore è u 14. // Qui operazioni su v15. ENQUEUE(Q,v) // e vanno in Q16. DEQUEUE(Q)17. color[u] ← BLACK // u nero: non più nella coda

Università degli Studi di Milano

Marco Frasca

BFS

● All’inizio tutti i vertici sono bianchi e, successivamente, possono diventare grigi e poi neri.

● La visita in ampiezza costruisce un albero BFS che all’inizio contiene solo la radice: il vertice sorgente s.

● Un vertice viene scoperto, la prima volta che viene incontrato durante la visita: in tale istante esso cessa di essere bianco.

Università degli Studi di Milano

Marco Frasca

ComplessitàUniversità degli Studi di Milano

Marco Frasca

Analisi del tempo di esecuzione su un grafo G=(V,E):

● Il tempo necessario per l’inizializzazione è O(|V|), tempo O(1) per ogni vertice.

● Ogni nodo raggiungibile viene visitato 1 volta:➢ Quando è bianco, appena estratto è colorato di grigio➢Le operazioni di inserimento e rimozione dalla coda è O(1), quindi il tempo totale per le operazioni sulla coda è O(|V|).➢ Di ogni vertice scoperto viene visitata tutta la lista di adia-cenza➢ Costo: archi presenti nelle liste di adiacenza dei nodi visitati. Quindi Θ(|E|).

• Sommando il tempo di inizializzazione e il tempo per visitare i vertici, si ha che l’algoritmo di BFS() viene eseguito in tempo O(|V| + |E|).

Cammino MinimoUniversità degli Studi di Milano

Marco Frasca

● Si definisce la distanza minima δ(s,v) ≥ 0 da s a v come il numero minimo di archi per passare dal vertice s al vertice v.

● Quando δ(s,v) = ∞, v risulta irraggiungibile partendo da s, ossia non esiste alcun cammino da s a v.

● Un cammino di lunghezza δ(s,v) da s a v è chiamato cammino minimo da s a v. (Possono esserci più cam-mini minimi!)

Cammino MinimoUniversità degli Studi di Milano

Marco Frasca

● Il vettore p definisce un sottografo di G, Tp=(Vp, E

p), dove:

● Vp = {s U v ∊ V: p[v] ≠ NIL}

● Ep = {(p[v], v) ∊ E: v ∊ V

p - {s} }

● Tp è un albero (albero BFS).

Proprietà: la lunghezza del cammino tra s e u in Tp è δ(s,u)

EsercizioUniversità degli Studi di Milano

Marco Frasca

1. Partendo dal codice per il grafo non diretto, scri-

vere un programma matlab che implementi un grafo

diretto.

2. Provare gli algoritmi BFS e DFS su tale grafo.