• Non ci sono risultati.

Scopo e tipi di visita

N/A
N/A
Protected

Academic year: 2022

Condividi "Scopo e tipi di visita"

Copied!
27
0
0

Testo completo

(1)

Grafi: visite

Una breve presentazione

(2)

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

Visite di grafi

(3)

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)

(4)

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

Algoritmo di visita generica

(5)

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

(6)

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 )

(7)

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.

(8)

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.

(9)

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

(10)

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

Visita in ampiezza

(11)

Visita in ampiezza

(12)

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

Esempio: grafo non orientato (1/2)

(13)

Esempio: grafo non orientato (2/2)

(14)

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

Esempio: grafo orientato

(15)

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

(16)

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.

(17)

Visita in profondità

(18)

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

Visita in profondità

(19)

Esempio: grafo non orientato (1/2)

(20)

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

Esempio: grafo non orientato (2/2)

(21)

Esempio: grafo orientato (1/2)

(22)

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

Esempio: grafo orientato (2/2)

(23)

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

(24)

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.

(25)

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à

(26)

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

(27)

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.

Riferimenti

Documenti correlati

Presentazione dell'impianto di biogas dell'azienda Cascone Nicola LABARTINO, Claudio FABBRI – CRPA spa, Reggio Emilia L'utilizzo agronomico del digestato. Paolo MANTOVI – CRPA

Più avanti ho notato altre baracche, in parte ricostruite, che, durante il periodo in cui il campo era un campo di transito, erano destinate agli oppositori politici.. La parte

Fare clic su , presente in corrispondenza della casella (della domanda) componente la visita, di cui si vuole personalizzare una o più risposta precompilata.. Si apre

N ella home care, la qualità e la buona riuscita non sono determinate dal solo atto medico. Il setting domiciliare non è standardizzato o stabile come l’o- spedale, le

Instant Pot è contemporaneamente una pentola a pressione elettrica, uno slow cooker (cottura lenta per ottenere effetti di cottura particolari), una macchina cuociriso, una

Le classi dovranno consegnare attraverso i loro rispettivi rappresentanti i permessi per l'uscita entro venerdì 12 aprile.. Ringrazio per la

Si raccomanda di far rispettare gli orari di visita a parenti ed amici per poter garantire ai genitori di vivere questo momento.. il più serenamente possibile, anche nel rispetto

Il motore incredibilmente silenzioso gira a una potenza di 1500W, con una garanzia di sette anni, ha il controllo continuo della velocità e un timer.. Le manopole sono in zinco