Grafi: visite, ordinamento topologico, componenti fortemente connessi PDF

Gra: visite, ordinamento topologico, componenti fortemente connessi May 7, 2020 Obiettivi: visitare gra in modo sistematico raccogliendo informazioni utili durante la visita. Argomenti: visita generale, visita in...

Gra: visite, ordinamento topologico, componenti fortemente connessi May 7, 2020 Obiettivi: visitare gra in modo sistematico raccogliendo informazioni utili durante la visita. Argomenti: visita generale, visita in ampiezza, visita in profondità, test di aciclicità, ordina- mento topologico, componenti fortemente connessi 1 Visita generica Si vuole visitare tutti i nodi di un grafo G = (V, E). La dicoltà rispetto a visitare alberi è dovuta agli eventuali cicli presenti nel grafo: possono esserci più cammini verso lo stesso nodo e quindi bisogna tener traccia dei nodi già visitati. Utilizziamo tre colori: bianco: nodi non ancora scoperti (non visitati), grigio: vertici scoperti di cui adiacenti non sono ancora tutti scoperti (nodi da cui bisogna andare ancora avanti; la frangia), nero: nodi scoperti di cui adiacenti sono già stati scoperti (nodi da cui non bisogna andare avanti più). L'algoritmo che inizializza la visita su G: Inizializza(G) for ∀v ∈ V do v.color ← bianco end for L'algoritmo che visita il grafo a partire dal nodo s: Visita(G, s) s.color ← grigio while ∃u ∈ V tale che u.color = grigio do u ← un nodo grigio if ∃v ∈ V tale che v.color = bianco ∧ (u, v) ∈ E then v ← un nodo tale che v.color = bianco ∧ (u, v) ∈ E v.color ← grigio else u.color ← nero end if end while L'algoritmo precedente è astratto nel senso che non denisce in che modo si sceglie un nodo fra quelli grigi e in che modo si rappresenta il grafo. Consideriamo il grafo seguente: 1  b e g a c f h d Simuliamo una possibile esecuzione di Visita(G, a) dopo aver inizializzato il grafo con Inizializza(G). La tabella indica l'ordine dei cambi di colore dei nodi e per ogni cambio bianco → grigio (tranne per il nodo a) indica l'arco utilizzato (u, v) dove u è il nodo grigio e v è il nodo bianco: 1 8 a : bianco −−−→ grigio −−−→ nero 2,(a,b) 4 b : bianco −−−−→ grigio −−−→ nero 5,(e,c) 7 c : bianco −−−−→ grigio −−−→ nero 6,(a,d) 12 d : bianco −−−−→ grigio −−−−→ nero 3,(b,e) 10 e : bianco −−−−→ grigio −−−−→ nero 9,(e,f ) 11 f : bianco −−−−→ grigio −−−−→ nero g : bianco h : bianco L'insieme dei nodi grigi cambia come segue: 1 2 3 4 5 6 7 8 9 10 11 12 {} − → {a} − → {a, b} − → {a, b, e} − → {a, e} − → {a, c, e} − → {a, c, d, e} − → {a, d, e} − → {d, e} − → {d, e, f } − −→ {d, f } − −→ {d} − −→ {} Un nodo diventa nero se viene scelto fra quelli grigi e non ha più adiacenti bianchi. I nodi g e h rimangono bianchi perché non sono raggiungibili dal nodo a. Invarianti del ciclo while di Visita(G, S ): I1 : gli adiacenti dei nodi neri sono grigi o neri I2 : tutti i vertici grigi o neri sono raggiungibili da s I3 : qualunque cammino da s ad un nodo bianco deve contenere almeno un vertice grigio Le invarianti I1 e I2 sono valide inizialmente ed è facile vedere che vengono mantenute dal ciclo. Per dimostrare l'invariante I3 consideriamo due casi: se s è ancora grigio allora è banalmente vero, se s è nero: assumiamo per assurdo che non c'è nessun vertice grigio sul cammino verso un nodo bianco; allora ci sarebbe un nodo bianco adiacente ad uno nero; ma questo contraddice all'invariante I1. Il seguente teorema aerma la correttezza di Visita(G, s). Teorema: Al termine di Visita(G, s): v.color = nero ⇐⇒ v è raggiungibile da s Dimostrazione: ⇒: segue dall'invariante I2. ⇐: l'invariante I3 e la condizione di uscita del ciclo implicano che non ci può essere nessun vertice bianco raggiungibile da s. Visita dell'intero grafo: se rimangono nodi bianchi allora si può ripartire da uno di essi per visitare l'intero grafo: 2  Visita-Tutti-Vertici(G) Inizializza(G) for ∀v ∈ V do if v.color = bianco then Visita(G, v ) end if end for La complessità della visita completa: Il costo associato con la gestione dei nodi dipende da come viene gestito l'insieme dei nodi grigi. Utilizziamo una struttura dati per rappresentare l'insieme dei nodi grigi e assumiamo che aggiungere e togliere un nodo ha costo costante (O(1)). Ogni nodo viene inserito e tolto dall'insieme dei grigi una volta a quindi il costo totale associato con i nodi è O(|V |). Il costo associato con la gestione degli archi dipende da come viene eettuato il controllo  If ∃v ∈ V tale che v.color = bianco ∧ (u, v) ∈ E then. Dato che un nodo non può ridiventare bianco, non è necessario percorrere la lista di adiacenti di u sempre dall'inizio ma si può continuare dalla posizione dove si è trovato un nodo bianco l'ultima volta. Questo implica che ogni lista viene percorsa una volta e il costo totale associato con gli archi è O(|E|). Segue che il costo totale della visita completa è O(|V | + |E|). 2 Visita in ampiezza La visita in ampiezza utilizza una coda per gestire l'insieme dei nodi grigi. Durante la visita per ogni nodo segniamo il predecessore e il numero di passi dal nodo dove la visita ha inizio. Inizializzazione: Inizializza(G) for ∀u ∈ V do u.color ← bianco u.π ← nil u.d ← ∞ end for La visita in ampiezza a partire dal nodo s: Visita(G, s) Q ← Empty-Queue s.color ← grigio s.π ← nil s.d ← 0 EnQueue(Q, s) while Non-Empty(Q) do u ← Front(Q) if ∃v ∈ V tale che v.color = bianco ∧ (u, v) ∈ E then v ← un nodo tale che v.color = bianco ∧ (u, v) ∈ E v.color ← grigio EnQueue(Q, v ) v.π ← u v.d ← v.u + 1 else u.color ← nero Dequeue(Q) end if end while Il primo elemento della coda rimane lo stesso nodo nché ha adiacenti bianchi. Per questo motivo si può inserire tutti gli adiacenti bianchi di u con un ciclo e poi togliere u dalla coda: 3  Visita(G, s) Q ← Empty-Queue s.color ← grigio s.π ← nil s.d ← 0 EnQueue(Q, s) while Non-Empty(Q) do u ← Front(Q) while ∃v ∈ V tale che v.color = bianco ∧ (u, v) ∈ E do v ← un nodo tale che v.color = bianco ∧ (u, v) ∈ E v.color ← grigio EnQueue(Q, v ) v.π ← u v.d ← v.u + 1 end while u.color ← nero Dequeue(Q) end while Consideriamo il grafo: b e g a c f h d Simuliamo l'algoritmo a partire prima dal nodo f e poi dal nodo g per visitare tutto il grafo. Gli attributi π deniscono una foresta dove i nodi con π = nil sono le radici e dove d indica il livello del nodo (fra parentesi gli attributi π e d): f (nil, 0) g(nil, 0) e(f, 1) h(g, 1) b(e, 2) c(e, 2) a(b, 3) d(a, 4) Proprietà della visita in profondità: al termine della visita in ampiezza a partire del nodo s: ∀v ∈ V, v.d = δ(s, v) dove δ(s, v) indica la distanza di v dal dal nodo s, cioè la lunghezza del cammino minimo da s a v in termini di numero di archi; per ogni vertice v raggiungibile da s, il cammino da s a v nella foresta generata dalla visita in ampiezza è un cammino minimo. 4 3 Visita in profondità La visita in profondità utilizza una pila per gestire l'insieme dei nodi grigi. Durante la visita per ogni nodo segniamo il predecessore e due attributi che, utilizzando un unico contatore chiamato time, segnano l'inizio visita (quando il nodo diventa grigio) e ne visita (quando il nodo diventa grigio) del nodo. Inizializzazione: Inizializza(G) for ∀u ∈ V do u.color ← bianco u.π ← nil u.i ← ∞ u.f ← ∞ end for time ← 1 La visita in profondità a partire dal nodo s: Visita(G, s) S ← Empty-Stack s.color ← grigio s.π ← nil s.i ← time time ← time + 1 Push(S, s) while Non-Empty(S ) do u← Top(S ) if ∃v ∈ V tale che v.color = bianco ∧ (u, v) ∈ E then v ← un nodo tale che v.color = bianco ∧ (u, v) ∈ E v.color ← grigio Push(S, v ) v.π ← u v.i ← time time ← time + 1 else u.color ← nero u.f ← time time ← time + 1 Pop(S ) end if end while (In questo caso non si può inserire tutti gli adiacenti bianchi di u nella pila con un ciclo perché tale modo di procedere non sarebbe più una visita in profondità.) Anche in questo caso la visita, grazie all'attributo π, genera una foresta. La visita completa del grafo precedente (a partire del nodo a a poi ripartendo dal nodo g) costruisce la seguente foresta dove per ogni nodo vengono indicati i e f: a(1, 12) g(13, 16) b(2, 9) d(10, 11) h(14, 15) e(3, 8) c(4, 5) f (6, 7) 5 La visita in profondità si può eettuare anche con un procedimento ricorsivo: Visita(G, s) s.color← grigio s.i ← time time ← time + 1 while ∃v ∈ V tale che v.color = bianco ∧ (s, v) ∈ E do v ← un nodo tale che v.color = bianco ∧ (s, v) ∈ E v.π ← s Visita(G, v ) end while s.f ← time time ← time + 1 s.color← nero Durante una visita in profondità è possibili classicare gli archi del grafo come segue: arco dell'albero: arco inserito nella foresta generata dalla visita, arco all'indietro: arco che collega un nodo ad un suo antenato in un albero della foresta, arco in avanti: arco che collega un nodo ad un suo discendente in un albero della foresta, arco di attraversamento: arco che collega due vertici che non sono in relazione antenato-discendente (fanno parte di due alberi distinti oppure di due rami distinti dello stesso albero). Se si disegnano i gli da sinistra a destra e gli alberi da sinistra a destra allora gli archi di attraversamento vanno da destra a sinistra. Un arco (u, v) viene classicato quando si esamina v nella lista di adiacenti di u. In quel momento v.color può essere: bianco: allora (u, v) è un arco della foresta generata della visita grigio: allora u è un discendente di v in un albero della foresta, e quindi (u, v) è un arco all'indietro nero: allora la visita di v è già terminata (e quindi v.f < u.f ), e quindi (u, v) è un arco  in avanti se v è un discendente di u e quindi se u.i