Grafi: visite
Una breve presentazione
F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)
Visite di grafi
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
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 esaminati
v∈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(n 2 )
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 generica riportato in precedenza NON è l’albero di scoperta (questo
perche’ 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.
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
Visita in ampiezza
F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)
Esempio: grafo non orientato (1/2)
Esempio: grafo non orientato (2/2)
F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)
Esempio: grafo orientato
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.
Visita in profondità
F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)
Visita in profondità
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)
Esempio: grafo orientato (1/2)
F. Damiani - Alg. & Lab. 04/05 (da C. Demetrescu et al - McGraw-Hill)
Esempio: grafo orientato (2/2)
Proprietà
• Sia (u,v) un arco di un grafo non orientato. Allora:
(u,v) è un arco dell’albero DFS, oppure
i 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, oppure
i 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.
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