Grafi: Visite PDF

Indice 1. Visita in generale 2. Visita in ampiezza...

Indice 1. Visita in generale 2. Visita in ampiezza 3. Visita in profondità Grafi: visite Corso di Algoritmi e strutture dati Corso di Laurea in Informatica Docenti: Ugo de’Liguoro, András Horváth Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 1/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 2/ 79 Sommario 1. Idea di base Obiettivo: I insieme di vertici diviso in tre sottoinsiemi: I visitare tutti nodi e archi in modo sistematico I bianco: nodi non ancora scoperti (non visitati) I grigio: vertici scoperti di cui adiacenti non sono ancora tutti scoperti (nodi da I problema di base in molte applicazioni cui bisogna andare ancora avanti; la frangia) I la visita fornisce informazione sul grafo visitato I nero: nodi scoperti di cui adiacenti sono già stati scoperti (nodi da cui non I vari tipi di visite: bisogna andare avanti più) I in ampiezza, breadth first search I in profondità, depth first search Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 3/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 4/ 79  1. Versione “astratta” dell’algoritmo 1. Proprietà, invarianti I I NIZIALIZZA(G) I proprietà I: colore di un nodo può solo passare da bianco a grigio a nero for ∀u ∈ V do I invariante I: se (u, v ) ∈ E e u è nero, allora v è grigio o nero u.color ← bianco I invariante II: tutti i vertici grigi o neri sono raggiungibili da s I V ISITA(G, s) I invariante III: qualunque cammino da s ad un nodo bianco deve contenere s.color ← grigio almeno un vertice grigio while ∃ nodo grigio do u ← nodo grigio if ∃v bianco ∈ adj[u] then v.color ← grigio else u.color ← black Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 5/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 6/ 79 1. Proprietà, invarianti 1. Al termine del algoritmo I invariante I e II sono evidenti I teorema: al termine dell’algoritmo I dimostrazione di invariante III: un vertice v è nero ⇐⇒ v è raggiungibile da s I se s è ancora grigio: vero I ⇒: dal’invariante II I se s è nero: se non ci fosse nessun vertice grigio, allora ci sarebbe un nodo I ⇐: invariante III e la condizione di uscita del ciclo implicano che non ci può bianco adiacente ad uno nero, che è impossibilie per l’invariante I essere nessun vertice bianco raggiungibile da s Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 7/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 8/ 79  1. Costruzione del sottografo di predecessori 1. Costruzione del sottografo di predecessori I per ogni vertice che viene scoperto, vogliamo ricordare quale vertice grigio ha I V ISITA(G, s) permesso di scoprirlo s.color ← grigio I vuole dire anche ricordare l’arco che ci porta alla scoperta del nodo while ∃ nodo grigio do I associamo ad ogni nodo un attributo (variabile) che memorizza il nodo dal u ← nodo grigio if ∃v bianco ∈ adj[u] then quale era scoperto v.color ← grigio I inizializzazione dell’algoritmo: v.π ← u I NIZIALIZZA(G) else for ∀u ∈ V do u.color ← black u.color ← bianco I proprietà II: al termine di VISITA(G, s), l’unico vertice nero con predecessore u.π ← nil nil è s Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 9/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 10/ 79 1. Sottografo di predecessori 1. Visitare grafi non connessi I sottografo: Gπ = (Vπ , Eπ ) I l’algoritmo precedente visita solo il componente di cui il nodo iniziale (s) fa I Vπ = {v ∈ V : v.π 6= nil} ∪ {s} parte I Eπ = {(v.π, v ) ∈ E : v ∈ Vπ − {s}} I visita tutto il grafo solo se il grafo è connesso I all’termine di VISITA(G, s), Vπ è l’insieme di tutti i vertici neri (tutti i nodi I visita intera di un grafo non connesso: raggiungibili da s) V ISITA -T UTTI -V ERTICI(G) I teorema: il sottografo di predecessori è un albero I NIZIALIZZA(G) for ∀u ∈ V do I dimostrazione: segue dal seguente invariante del while: Gπ = (Vπ , Eπ ) è if u.color = bianco then connesso e |Eπ | = |Vπ | − 1 V ISITA(G, u) I il sottografo Gπ = (Vπ , Eπ ) è l’albero di scoperta I il sottografo di predecessori diventa una foresta (un grafo composto da più alberi) se il grafo contiene più componenti I questa foresta si chiama foresta di scoperta Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 11/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 12/ 79  1. Cammino di scoperta 1. Versione “concreta” dell’algoritmo I algoritmo che stampa il cammino dal sorgente della visita ad un nodo u I una struttura dati D per gestire l’insieme di vertici grigi P RINT-PATH(G, s, u) I operazioni necessari: if u = s then I M AKE -E MPTY: crea una struttura nuova stampa u I F IRST(D): restituisce il primo elemento (senza modificare D) I A DD(D, x): aggiunge l’elemento x a D else I R EMOVE -F IRST(D): toglie da D il primo elemento if u.π = nil then I N OT-E MPTY(D): restituisce true se D non è vuoto, false altrimenti stampa “non esiste cammino da s ad u” I ruolo di A DD(D, x): else I aggiunge x come primo elemento → pila (stack) P RINT-PATH(G, s, u.π) I aggiunge x come ultimo elemento → coda (queue) stampa u Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 13/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 14/ 79 1. Versione “concreta” dell’algoritmo 1. Complessità della visita V ISITA(G, s) I bisogna sapere come viene implementato il test: D ← M AKE -E MPTY if ∃v bianco ∈ adj[u] s.color ← grigio I assumiamo di aver realizzato il test con ciclo che percorre dall’inizio la lista di A DD(D, s) adiacenza while N ON -E MPTY(D) do I ciclo finisce quando si trova il primo nodo bianco u ← F IRST(D) if ∃v bianco ∈ adj[u] then I problema: la lista di adiacenza di un nodo u può essere percorso più volte v.color ← grigio v.π ← u A DD(D, v ) else u.color ← black R EMOVE -F IRST(D) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 15/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 16/ 79  1. Complessità della visita 1. Complessità della visita I dalla proprietà I sappiamo che un vertice grigio o nero non può ridiventare I inizializzazione richiede tempo O(|V |) bianco I ogni vertice viene inserito (eliminato) una volta in (da) D I non è necessario percorrere la lista di adiacenza dal inizio I assumiamo che le operazioni di inserimento e eliminazione richiedano un I il ciclo può partire da dove è arrivato l’ultima volta tempo costante I associamo ad ogni vertice il valore corrente del puntatore alla lista di adiacenti I tempo totale dedicato alle operazioni su D è O(|V |) I la lista di adiacenza è percorsa una volta sola → implementazione più I le liste di adiacenza vengono percorse una volta efficiente I tempo totale dedicato alla ricerca di nodi bianchi è O(|E|) I tempo totale: O(|V | + |E|) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 17/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 18/ 79 2. Visita in ampiezza 2. Esempio di BFS I V ISITA(G, s) B F A D ← M AKE -E MPTY s.color ← grigio A C E G A DD(D, s) while N ON -E MPTY(D) do u ← F IRST(D) D H if ∃v bianco ∈ adj[u] then v.color ← grigio v.π ← u Coda D: A DD(D, v ) A else u.color ← black R EMOVE -F IRST(D) I D è una coda → visita in ampiezza (breadth first search, BFS) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 19/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 20/ 79  2. Esempio di BFS 2. Esempio di BFS B F A B F A A C E G B D A C E G B D D H D H A B D B D Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 21/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 22/ 79 2. Esempio di BFS 2. Esempio di BFS B F A B F A A C E G B D A C E G B D D H C F D H C F B D C F D C F Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 23/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 24/ 79  2. Esempio di BFS 2. Esempio di BFS B F A B F A A C E G B D A C E G B D D H C F H D H C F H E C F H F H E Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 25/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 26/ 79 2. Esempio di BFS 2. Esempio di BFS B F A B F A A C E G B D A C E G B D D H C F H D H C F H E G E G H E G E G Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 27/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 28/ 79  2. Esempio di BFS 2. Esempio di BFS B F A B F A A C E G B D A C E G B D D H C F H D H C F H E G E G G Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 29/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 30/ 79 2. Versione modificata dell’algoritmo 2. Terza versione (ancora più “concreta”) V ISITA(G, s) I il primo elemento della coda non cambia finchè ci sono adiacenti bianchi D ← M AKE -E MPTY I V ISITA(G, s) s.color ← grigio D ← M AKE -E MPTY A DD(D, s) s.color ← grigio while N ON -E MPTY(D) do Ogni elemento nella lista di u ← F IRST(D) A DD(D, s) adiacenti ha due campi: ptr ← adj[u] while N ON -E MPTY(D) do while ptr 6= nil do u ← F IRST(D) I vtx è la vertice v ← ptr.vtx for ∀v : v è bianco ed è ∈ adj[u] do I next è il prossimo if v.color = bianco then v.color ← grigio elemento nella lista v.color ← grigio v.π ← u v.π ← u A DD(D, v ) A DD(D, v ) ptr ← ptr.next u.color ← black R EMOVE -F IRST(D) u.color ← black R EMOVE -F IRST(D) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 31/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 32/ 79  2. Albero di BFS 2. Albero di BFS I albero di BFS viene costruito a livelli I algoritmo di visita BFS col calcolo del livello : I la costruzione del livello n + 1 non comincia prima di concludere la I I NIZIALIZZA(G) costruzione del livello n for ∀u ∈ V do A u.color ← bianco u.π ← nil u.d ← ∞ B D C F H E G I associamo ad ogni nodo un attributo (d) che ricorda il livello del nodo Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 33/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 34/ 79 2. Albero di BFS 2. Albero di BFS V ISITA(G, s) I albero dipende dal ordine in cui i nodi sono elencati nelle liste di adiecenza: D ← M AKE -E MPTY lista di adiecenza in ordine lista di adiecenza in ordine s.color ← grigio alfabetico: inverso: s.d ← 0 A A A DD(D, s) while N ON -E MPTY(D) do B D D B u ← F IRST(D) for ∀v : v è bianco ed è ∈ adj[u] do C F H H C F v.color ← grigio v.π ← u E G G E v.d ← u.d + 1 A DD(D, v ) u.color ← black R EMOVE -F IRST(D) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 35/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 36/ 79  2. Proprietà della visita BFS 2. Proprietà della visita BFS Ma ogni nodo rimane allo stesso livello: I per ogni vertice v raggiungibile da s, il cammino da s a v nell’albero BFS è un A A cammino minimo I il livello di un nodo nell’albero ottenuto con la visita BFS è indipendente dal B D D B ordine in cui sono memorizzati i vertici nelle liste di adiacenza C F H H C F E G G E I teorema: al termine della visita BFS ∀v ∈ V , v.d = δ(s, v ) dove δ(s, v ) indica la distanza di v dal sorgente s della visita (lunghezza di cammino minimo) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 37/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 38/ 79 3. Visita in profondità 3. Esempio di DFS I V ISITA(G, s) B H A D ← M AKE -E MPTY s.color ← grigio A C D E A DD(D, s) while N ON -E MPTY(D) do u ← F IRST(D) G F if ∃v bianco ∈ adj[u] then v.color ← grigio Pila: v.π ← u A DD(D, v ) A else u.color ← black R EMOVE -F IRST(D) I D è una pila → visita in profondità (depth first search, DFS) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 39/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 40/ 79  3. Esempio di DFS 3. Esempio di DFS B H A B H A B B A C D E A C D E C G F G F Pila D: Pila D: A B A B C Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 41/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 42/ 79 3. Esempio di DFS 3. Esempio di DFS B H A B H A B B A C D E A C D E C C G F G F D D Pila D: Pila D: F F A B C D F E H A B C D F E E E H H Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 43/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 44/ 79  3. Esempio di DFS 3. Esempio di DFS B H A B H A B B A C D E A C D E C C G F G F D D Pila D: Pila D: F F A B C D F A B C D F G E E G H H Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 45/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 46/ 79 3. Esempio di DFS 3. Esempio di DFS B H A B H A B B A C D E A C D E C C G F G F D D Pila D: Pila D: F F A B C D F A B C D E G E G H H Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 47/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 48/ 79  3. Esempio di DFS 3. Esempio di DFS B H A B H A B B A C D E A C D E C C G F G F D D Pila D: Pila D: F F A B C E G E G H H Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 49/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 50/ 79 3. Ordine di scoperta di nodi 3. Ordine di scoperta di nodi I due ordini tra i nodi: I liste di adiacenza in ordine contrario I l’ordine in cui i nodi diventano grigi A 1 8 A 1 8 (scritto nel nodo) I l’ordine in cui i nodi diventano neri B 2 7 G 2 7 (scritto accanto al nodo) I liste di adiacenza in ordine alfabetico C 3 6 F 3 6 7 1 E 4 5 7 1 D 4 5 B 8 H 5 B 2 H 7 8 6 H 5 4 2 6 F 5 4 A 1 C 7 D 6 E 4 8 2 5 A 1 C 3 D 4 E 6 D 6 3 5 E 6 2 G 8 3 G 2 F 3 4 C 7 2 3 G 8 F 5 4 H 7 1 B 8 1 3 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 51/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 52/ 79  3. Ordine di scoperta di nodi 3. Versione sbagliata (non funziona) A 1 16 A 1 16 I V ISITA(G, s) B 2 15 G 2 15 D ← M AKE -E MPTY s.color ← grigio C 3 14 F 3 14 A DD(D, s) I un unico contatore che viene while N ON -E MPTY(D) do incrementato quando un nodo D 4 13 E 4 13 u ← F IRST(D) cambia colore for ∀v : v è bianco ed è ∈ adj[u] do I ogni nodo viene marcato due volte F 5 12 H 5 12 v.color ← grigio con questo numero (bianco → v.π ← u grigio, grigio → nero) E 6 9 G 10 11 D 6 11 A DD(D, v ) u.color ← black H 7 8 C 7 10 R EMOVE -F IRST(D) B 8 9 I perchè non funziona? Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 53/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 54/ 79 3. Perchè non funziona? 3. Una versione corretta I se v è bianco, diventa grigio e finisce sul top di D V ISITA(G, s) I la lista di adiacenti da considerare dovrebbe essere quella del nuovo nodo sul D ← M AKE -E MPTY top di D s.color ← grigio A DD(D, s) I invece nella condizione del for rimane il vertice precedente while N ON -E MPTY(D) do while ∃v : v è bianco ed è ∈ adj[F IRST(D)] do v.color ← grigio v.π ← F IRST(D) A DD(D, v ) u.color ← black R EMOVE -F IRST(D) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 55/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 56/ 79  3. E una versione corretta e più concreta 3. Inizializzazione V ISITA(G, s) I naturalmente l’attributo ptr va inizializzato D ← M AKE -E MPTY I I NIZIALIZZA(G) s.color ← grigio for ∀u ∈ V do A DD(D, s) u.color ← bianco while N ON -E MPTY(D) do u.π ← nil while F IRST(D).ptr 6= nil do u.ptr ← adj[u] v ← F IRST(D).ptr.vtx F IRST(D).ptr ← F IRST(D).ptr.next if v.color = bianco then v.color ← grigio v.π ← F IRST(D) A DD(D, v ) F IRST(D).color ← black R EMOVE -F IRST(D) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 57/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 58/ 79 3. Un altro esempio di DFS 3. Un altro esempio di DFS A D A A D A D B F B C B C C E F E F Pila: Pila: A A D B F C Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 59/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 60/ 79  3. Un altro esempio di DFS 3. Un altro esempio di DFS A D A A D A D D B B F F B C C B C C C C E E F E F Pila: Pila: A D B F A D B F E Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 61/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 62/ 79 3. Un altro esempio di DFS 3. Un altro esempio di DFS A D A A D A D D B B F F B C C B C C C C E E E F E F E E F Pila: Pila: A D B F A D B Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 63/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 64/ 79  3. Un altro esempio di DFS 3. Un altro esempio di DFS A D A A D A D D B B F F B C C B C C C C E E E F E F E E F F Pila: B Pila: B D A D A Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 65/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 66/ 79 3. Un altro esempio di DFS 3. Struttura di “attivazione” A D A A D D B B F F B C C C C I gli intervalli di “attivazione” di una qualunque E coppia di nodi sono: C E F E I disgiunti oppure E F I uno interamente contenuto nell’altro E Pila: B D F A B D A Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 67/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 68/ 79  3. Struttura di “attivazione” 3. Versione ricorsiva della visita in profondità A 1 12 V ISITA(G, s) s.color ← grigio while ∃v : v è bianco ed è ∈ adj[s] do I un vertice non viene “disattivato” finchè non D 2 11 v.π ← s sono stati “attivati” e “disattivati” tutti i suoi V ISITA(G, v ) discendenti s.color ← nero I è l’ordine in cui si percorre l’albero delle B 3 10 chiamate ricorsiva di una procedura ricorsiva I progettiamo una versione ricorsiva F 4 9 dell’algoritmo di visita in profondità C 5 6 E 7 8 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 69/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 70/ 79 3. Corrispondenza fre la versione ricorsiva e iterativa 3. Versione estesa per raccogliere altre informazioni I c’è corrispondenza fra lo stack della versione iterativa e lo stack delle I introduciamo un contatore “time” per ricordare l’ordine delle attivazioni e attivazioni della procedura ricorsiva disattivazioni I supponiamo che le due versioni visitino gli adiacenti nello stesso ordine I V ISITA(G, s) I se il contenuto dello stack della versione iterativa è {v1 ,..., vr } (v1 = s e vr è s.color ← grigio al top dello stack) s.d ← time I allora la sequenza di attivazioni per la procedura ricorsiva è time ← time + 1 while ∃v : v è bianco ed è ∈ adj[s] do {V ISITA(G, v1 ),...,V ISITA(G, vr )} v.π ← s I può essere dimostrata per induzione sul numero di elementi nello stack V ISITA(G, v ) s.f ← time time ← time + 1 s.color ← nero Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 71/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 72/ 79  3. Versione estesa per raccogliere altre informazioni 3. Visita in profondità di tutti i nodi I bisogna inizializzare le nuove variabili: I l’algoritmo precedente visita solo il componente di cui il nodo iniziale (s) fa I I NIZIALIZZA(G) parte for ∀u ∈ V do I visita tutto il grafo solo se il grafo è connesso u.color ← bianco I visita intera di un grafo non connesso: u.π ← nil V ISITA -T UTTI -V ERTICI(G) u.d ← ∞ I NIZIALIZZA(G) u.f ← ∞ for ∀u ∈ V do time ← 1 if u.color = bianco then I tempi di un nodo non visitato rimangono infiniti V ISITA(G, u) Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 73/ 79 Algoritmi e strutture dati, Ugo de’Liguoro, András Horváth 74/ 79 3. Proprietà della visita in profondità di tutti i nodi 3. Proprietà della visita in profondità di tutti i nodi I Teorema delle parentesi: in ogni visita DFS in un grafo (orientato o non I classificazione degli archi del grafo durante DFS orientato), per ogni coppia di nodi u, v , una e una sola delle seguente I arco dell’albero: arco inserito nella foresta DFS condizioni è soddisfatta: I arco all’indietro: arco che collega un nodo ad un suo antenato I u.d