F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Grafi: visite

Una breve presentazione

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Visite di grafi

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Scopo e tipi di visita

• Una visita (o attraversamento) di un grafo G permette di esaminare i nodi e gli archi di G in modo sistematico

• Problema di base in molte applicazioni• Esistono vari tipi di visite con diverse

proprietà: in particolare, visita in ampiezza (BFS=breadth first search) e visita in profondità (DFS=depth first search)

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Algoritmo di visita generica

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Osservazioni

• Un vertice viene marcato quando viene incontrato per la prima volta: la marcatura può essere mantenuta tramite un vettore di bit di marcatura

• La visita genera un albero di copertura T del grafo• L’insieme di vertici F⊆T mantiene la frangia di T:

v∈T-F: v è chiuso, tutti gli archi incidenti su v sono stati esaminativ∈F: v è aperto, esistono archi incidenti su v non ancora esaminati

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Costo della visita

Il tempo di esecuzione dipende dalla struttura dati usata per rappresentare il grafo:

• Lista di archi: O(mn)• Liste di adiacenza: O(m+n)• Matrice di adiacenza: O(n2)

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Osservazione

• Nell’algoritmo di visita generica i vertici sono visitati in un momento successivo a quello in cui sono scoperti (marcati). Quindi: l’ordine in cui i vertici sono scoperti (marcati) NON coincide con l’ordine in cui sono visitati.

F. Damiani - Alg. & Lab. 04/05

L’“albero di scoperta”• Definiamo albero di scoperta l’albero di copertura del grafo

che, per ogni vertice che è stato scoperto durante la visita, tiene traccia di quale vertice ha permesso di scoprirlo (ossia contiene l’arco percorso per scoprirlo).

• In generale, l’albero restituito dall’algoritmo di visita genericariportato in precedenza NON è l’albero di scoperta (questoperche’ l’else che puo’ cambiare il padre di un nodo).

• L’algoritmo ottenuto dall’algoritmo di visita generica riportato in precedenza rimuovendo l’else, restituisce l’albero di scoperta. In generale, tale albero NON “riflette l’ordine in cui sono stati visitati i nodi”, perche’ i nodi possono essere visitati successivamente alla loro scoperta.

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Visite particolari• Se la frangia F è implementata come coda si ha la

visita in ampiezza (BFS)• Se la frangia F è implementata come pila si ha la

visita in profondità (DFS). ATTENZIONE: (come sarà evidente dopo che avremo esaminato gli algoritmi di visita in ampiezza e profondità ) per ottenere (dal particolare algoritmo di visita generica riportato in precedenza) un algoritmo di visita in ampiezza che restituisca un albero che “rifletta l’ordine in cui sono stati visitati i vertici” è sufficiente rendere F una coda e rimuovere l’else. Invece, per ottenere un algoritmo di visita in profondita’ che restituisca un albero che “rifletta l’ordine in cui sono stati visitati i vertici” non basta rendere F una pila: sono necessarie altre modifiche (il significato della locuzione “rifletta l’ordine in cui sono stati visitati i vertici” sarà più chiaro dopo che avremo esaminato gli algoritmi di visita in ampiezza e profondità).

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Visita in ampiezza

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Visita in ampiezza

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Esempio: grafo non orientato (1/2)

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Esempio: grafo non orientato (2/2)

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Esempio: grafo orientato

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Proprietà

• Per ogni nodo v, il livello di v nell’albero BFS è pari alla distanza di v dalla sorgente s

• Per ogni arco (u,v) di un grafo non orientato, gli estremi u e v appartengono allo stesso livello o a livelli consecutivi dell’albero BFS

• Se il grafo è orientato, possono esistere archi (u,v) che attraversano all’indietro più di un livello

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Osservazione

• Nell’algoritmo di visita in ampiezza i vertici sono visitati nel momento stesso in cui sono scoperti (marcati). Quindi: l’ordine in cui i vertici sono scoperti (marcati) coincide con l’ordine in cui sono visitati.

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Visita in profondità

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Visita in profondità

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Esempio: grafo non orientato (1/2)

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Esempio: grafo non orientato (2/2)

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Esempio: grafo orientato (1/2)

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Esempio: grafo orientato (2/2)

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Proprietà

• Sia (u,v) un arco di un grafo non orientato. Allora: (u,v) è un arco dell’albero DFS, oppurei nodi u e v sono l’uno discendente/antenato dell’altro

• Sia (u,v) un arco di un grafo orientato. Allora: (u,v) è un arco dell’albero DFS, oppurei nodi u e v sono l’uno discendente/antenato dell’altro,

oppure(u,v) è un arco trasversale a sinistra, ovvero il vertice v è in un sottoalbero visitato precedentemente ad u

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Osservazione

• Nell’algoritmo di visita in profondità i vertici sono visitati nel momento stesso in cui sono scoperti (marcati). Quindi: l’ordine in cui i vertici sono scoperti (marcati) coincide con l’ordine in cui sono visitati.

F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)

Riepilogo (1/2)• Concetto di grafo e terminologia• Diverse strutture dati per rappresentare grafi nella

memoria di un calcolatore• L’utilizzo di una particolare rappresentazione può

avere un impatto notevole sui tempi di esecuzione di un algoritmo su grafi (ad esempio, nella visita di un grafo)

• Algoritmo di visita generica e due casi particolari: visita in ampiezza e visita in profondità

F. Damiani - Alg. & Lab. 04/05

Riepilogo (2/2)• Nelle visite in ampiezza e profondità i vertici

sono visitati nel momento stesso in cui sono scoperti.

• L’albero BFS e l’albero DFS (che coincidono con gli alberi di scoperta generati, rispettivamente, dalle visite in ampiezza e profondità ) “riflettono l’ordine in cui sono stati visitati i vertici”.

F. Damiani - Alg. & Lab. 04/05

Esercizio• Considerate l’algoritmo ottenuto dall’algoritmo di visita

generica riportato in precedenza rimuovendo l’else e rendendo F una pila.

Dimostrate che tale algoritmo visita i nodi in un ordine che è quello della visita in profondita’, ma che restituisce un albero (l’“albero di scoperta dei nodi”) che, in generale, NON e’ un albero DFS.Modificate tale algoritmo in modo da ottenere un algoritmo (di visita in profondita’) che restituisca un albero DFS. Suggerimento: dovete scoprire i vertici nell’ordine in cui devono essere visitati.