1.6 Visita di un grafo¶
Parte 1 · Grafi · Capitolo 1 · Capitolo 1: Grafi · Dispensa, volume 1 (PDF) · Slide · Esercizi: Grafi · App: Ricerca su grafo: BFS e DFS
Definizione 1.24: visita di un grafo
Dati un grafo orientato \(G=(N,A)\) e un nodo \(s \in N\), la sorgente, una visita di un grafo trova l'insieme \(R(s)\) dei nodi raggiungibili da \(s\). Durante la visita:
-
un nodo è etichettato quando la visita lo raggiunge, e resta etichettato;
-
ogni nodo etichettato \(j \neq s\) registra il suo predecessore \(\mathit{pred}(j)\), il nodo da cui è stato raggiunto;
-
i nodi etichettati ancora da elaborare sono tenuti in una lista, \(\mathit{LIST}\);
-
un arco \((i,j)\) è ammissibile se \(i\) è etichettato e \(j\) no.
Algoritmo: Visita generica di un grafo
STOP. Altrimenti selezionare un nodo \(i \in \mathit{LIST}\):-
Nella BFS la lista \(\mathit{LIST}\) è una coda (first in, first out): i nodi sono elaborati nell'ordine in cui sono etichettati.
-
Nella DFS la lista \(\mathit{LIST}\) è una pila (last in, first out): la visita riparte sempre dal nodo etichettato più di recente ancora in \(\mathit{LIST}\), e torna indietro solo quando quel nodo non ha archi ammissibili.
-
L'ordine delle liste di adiacenza decide quale arco ammissibile si prende per primo; con le liste ordinate per indice crescente, come in questo modulo, il risultato è unico.
1.6.1 L'albero dei predecessori¶
Proposizione 1.25: albero dei predecessori
A ogni iterazione, gli archi \((\mathit{pred}(j),j)\), per i nodi etichettati \(j \neq s\), formano un albero sui nodi etichettati, l'albero dei predecessori. Per ogni nodo etichettato \(j\) esso contiene un cammino orientato da \(s\) a \(j\).
Dimostrazione
Sia \(r\) il numero di nodi etichettati.
-
Ogni nodo etichettato \(j \neq s\) ha un predecessore, etichettato prima di \(j\). Partendo da \(j\) e passando al predecessore, i nodi sono etichettati sempre prima, quindi la sequenza termina in \(s\).
-
Letta all'indietro, è un cammino orientato da \(s\) a \(j\) lungo gli archi \((\mathit{pred}(h),h)\).
-
Quindi gli \(r-1\) archi connettono gli \(r\) nodi etichettati, e formano un albero per il Teorema 1.17(b). □
Teorema 1.26: correttezza della visita
Al termine della visita generica, BFS e DFS comprese, i nodi etichettati sono esattamente i nodi di \(R(s)\).
Dimostrazione
Ogni nodo etichettato è raggiungibile da \(s\), per la Proposizione 1.25. Viceversa, sia \(j \in R(s)\) e sia \(s=i_0,i_1,\dots,i_k=j\) un cammino orientato; supponiamo per assurdo che \(j\) non sia etichettato.
-
Sia \(i_t\) il primo nodo non etichettato del cammino; \(t \ge 1\), perché \(s\) è etichettato.
-
Il nodo \(i_{t-1}\) è etichettato, quindi è entrato in \(\mathit{LIST}\), e alla fine ne è uscito.
-
Un nodo esce da \(\mathit{LIST}\) solo quando non ha archi ammissibili. Ma \((i_{t-1},i_t)\) resta ammissibile fino alla fine, perché le etichette non si tolgono mai: una contraddizione. □
Teorema 1.27: tempo di esecuzione della visita
Con le liste di adiacenza, la visita generica richiede tempo \(O(|N|+|A|)\).
Dimostrazione
Ogni nodo mantiene un puntatore alla posizione corrente nella sua lista \(L(i)\); il puntatore avanza oltre i successori etichettati e non torna mai indietro, perché le etichette non si tolgono mai.
-
Ogni iterazione etichetta un nodo o rimuove un nodo da \(\mathit{LIST}\). Ogni nodo è etichettato al più una volta e rimosso al più una volta, quindi ci sono al più \(2n\) iterazioni, ciascuna con lavoro \(O(1)\) oltre al puntatore.
-
Il puntatore del nodo \(i\) avanza in tutto al più \(\deg^+(i)\) volte, e \(\sum_{i \in N} \deg^+(i)=m\).
Il tempo totale è \(O(n+m)=O(|N|+|A|)\). □
- Con la matrice di adiacenza i successori di un nodo si trovano scorrendo una riga di lunghezza \(n\), e la visita richiede tempo \(O(n^2)\).
1.6.2 La visita in ampiezza sul grafo di riferimento¶
Esempio 1.9: BFS dal nodo \(1\)
Eseguiamo la BFS sul grafo di riferimento da \(s=1\), con le liste di adiacenza dell'Esempio 1.5. Ogni riga è un'iterazione, e \(\mathit{LIST}\) è riportata dopo di essa:
| iterazione | \(i\) selezionato | azione | \(\mathit{LIST}\) |
|---|---|---|---|
| \(1\) | \(1\) | etichetta \(2\), \(\mathit{pred}(2)=1\) | \(1,2\) |
| \(2\) | \(1\) | etichetta \(3\), \(\mathit{pred}(3)=1\) | \(1,2,3\) |
| \(3\) | \(1\) | rimuovi \(1\) | \(2,3\) |
| \(4\) | \(2\) | etichetta \(4\), \(\mathit{pred}(4)=2\) | \(2,3,4\) |
| \(5\) | \(2\) | rimuovi \(2\) | \(3,4\) |
| \(6\) | \(3\) | etichetta \(5\), \(\mathit{pred}(5)=3\) (\(2\) è etichettato) | \(3,4,5\) |
| \(7\) | \(3\) | rimuovi \(3\) | \(4,5\) |
| \(8\) | \(4\) | etichetta \(6\), \(\mathit{pred}(6)=4\) (\(3\) è etichettato) | \(4,5,6\) |
| \(9\) | \(4\) | rimuovi \(4\) | \(5,6\) |
| \(10\) | \(5\) | rimuovi \(5\) (\(4\) e \(6\) sono etichettati) | \(6\) |
| \(11\) | \(6\) | rimuovi \(6\) | (vuota) |
L'ordine di etichettatura è \(1,2,3,4,5,6\): ogni nodo è raggiungibile da \(1\). L'albero dei predecessori ha gli archi \((1,2)\), \((1,3)\), \((2,4)\), \((3,5)\), \((4,6)\); è l'albero ricoprente dell'Esempio 1.7. Accanto a ogni nodo, la figura riporta il numero \(d(j)\) di archi del cammino dell'albero da \(1\) a \(j\).
Proposizione 1.28: la BFS trova i cammini più corti in numero di archi
Nell'albero dei predecessori della BFS, siano \(d(s)=0\) e \(d(j)=d(\mathit{pred}(j))+1\) per ogni nodo etichettato \(j \neq s\). Allora, per ogni \(j \in R(s)\), \(d(j)\) è il numero minimo di archi di un cammino orientato da \(s\) a \(j\).
Dimostrazione
Dimostriamo tre fatti.
-
Se \(\mathit{LIST}=u_1,u_2,\dots,u_r\), allora \(d(u_1) \le d(u_2) \le \dots \le d(u_r) \le d(u_1)+1\). Vale al Passo 0. Un nuovo nodo \(j\) è etichettato da \(u_1\) e aggiunto con \(d(j)=d(u_1)+1\); rimuovere \(u_1\) mantiene la proprietà, perché \(d(u_r) \le d(u_1)+1 \le d(u_2)+1\).
-
I nodi sono etichettati in ordine non decrescente di \(d\). Ogni nuovo nodo ha \(d(j)=d(u_1)+1 \ge d(u_r)\), e \(u_r\) è l'ultimo nodo etichettato prima di \(j\).
-
Per ogni arco \((i,j)\) con \(i\) etichettato, \(d(j) \le d(i)+1\). Se \(j\) è etichettato dopo \(i\), allora \(j\) è etichettato prima che \(i\) esca da \(\mathit{LIST}\), da un nodo \(u\) in testa a \(\mathit{LIST}\), etichettato non dopo \(i\): \(d(j)=d(u)+1 \le d(i)+1\). Se \(j\) è etichettato prima di \(i\), allora \(d(j) \le d(i)\) per il fatto 2.
Sia \(s=i_0,i_1,\dots,i_k=j\) un cammino orientato con il numero minimo \(k\) di archi. I suoi nodi sono etichettati (Teorema 1.26), e per il fatto 3 \(d(j) \le d(i_{k-1})+1 \le \dots \le d(s)+k=k\). Il cammino dell'albero da \(s\) a \(j\) è un cammino orientato con \(d(j)\) archi, quindi \(d(j) \ge k\). □
- Nell'Esempio 1.9, i valori \(d=(0,1,1,2,2,3)\) sono i numeri minimi di archi dal nodo \(1\): per esempio, i cammini orientati più corti verso il nodo \(6\) hanno \(3\) archi, come \(1,2,4,6\).
1.6.3 La visita in profondità sul grafo di riferimento¶
Esempio 1.10: DFS dal nodo \(1\)
Eseguiamo la DFS sul grafo di riferimento da \(s=1\): il nodo selezionato è sempre l'ultimo di \(\mathit{LIST}\).
| iterazione | \(i\) selezionato | azione | \(\mathit{LIST}\) |
|---|---|---|---|
| \(1\) | \(1\) | etichetta \(2\), \(\mathit{pred}(2)=1\) | \(1,2\) |
| \(2\) | \(2\) | etichetta \(4\), \(\mathit{pred}(4)=2\) | \(1,2,4\) |
| \(3\) | \(4\) | etichetta \(3\), \(\mathit{pred}(3)=4\) | \(1,2,4,3\) |
| \(4\) | \(3\) | etichetta \(5\), \(\mathit{pred}(5)=3\) (\(2\) è etichettato) | \(1,2,4,3,5\) |
| \(5\) | \(5\) | etichetta \(6\), \(\mathit{pred}(6)=5\) (\(4\) è etichettato) | \(1,2,4,3,5,6\) |
| \(6\) | \(6\) | rimuovi \(6\) | \(1,2,4,3,5\) |
| \(7\) | \(5\) | rimuovi \(5\) | \(1,2,4,3\) |
| \(8\) | \(3\) | rimuovi \(3\) | \(1,2,4\) |
| \(9\) | \(4\) | rimuovi \(4\) (\(3\) e \(6\) sono etichettati) | \(1,2\) |
| \(10\) | \(2\) | rimuovi \(2\) | \(1\) |
| \(11\) | \(1\) | rimuovi \(1\) (\(2\) e \(3\) sono etichettati) | (vuota) |
L'ordine di etichettatura è \(1,2,4,3,5,6\), e l'albero dei predecessori ha gli archi \((1,2)\), \((2,4)\), \((4,3)\), \((3,5)\), \((5,6)\): un unico cammino orientato. Accanto a ogni nodo, la figura riporta la sua posizione \(o(j)\) nell'ordine di etichettatura.
- Entrambe le visite etichettano tutti i nodi, come garantisce il Teorema 1.26, ma i loro alberi sono diversi. L'albero della DFS raggiunge il nodo \(6\) con \(5\) archi, quello della BFS con \(3\).
1.6.4 Usare la visita¶
-
Componenti connesse. In un grafo non orientato, una visita da un vertice non etichettato etichetta tutta la sua componente; ripeterla da ogni vertice ancora non etichettato trova tutte le componenti in tempo \(O(n+m)\).
-
Componenti fortemente connesse. Una visita in \(G\) e una nel grafo invertito \(G'\) danno \(R(i)\) e \(R'(i)\), quindi \(S(i)=R(i) \cap R'(i)\); ripeterle per un nodo di ogni componente ancora sconosciuta richiede tempo \(O(n(n+m))\).
-
Alberi ricoprenti. Su un grafo non orientato connesso, l'albero dei predecessori di una visita da un vertice qualsiasi è un albero ricoprente.
Una visita di un grafo etichetta esattamente i nodi raggiungibili dalla sorgente, in tempo \(O(|N|+|A|)\), e i suoi predecessori formano un albero. La BFS (una coda) dà cammini con il numero minimo di archi; la DFS (una pila) va prima in profondità.
1.7 Errori tipici¶
Attenzione
-
Scambiare i segni della matrice di incidenza. L'elemento è \(+1\) nella coda e \(-1\) nella testa: la colonna di \((4,3)\) ha \(+1\) nella riga \(4\).
-
Chiamare cammino una passeggiata. Un cammino ha vertici distinti; una passeggiata può ripeterli, e contiene sempre un cammino con gli stessi estremi.
-
Confondere connessione debole e forte. Il grafo di riferimento è debolmente connesso, ma ha tre componenti fortemente connesse.
-
Contare solo gli spigoli. Un grafo con \(n-1\) spigoli non è necessariamente un albero: deve anche essere connesso, oppure aciclico.
-
Credere che la matrice di incidenza abbia rango pieno per righe. Il suo rango è \(|N|-k\): in un grafo connesso una riga è sempre ridondante.
-
Aspettarsi cammini più corti dalla DFS. Solo l'albero della BFS dà il numero minimo di archi, e solo quando ogni arco conta uno.
-
Dimenticare l'ordine delle liste. L'ordine di etichettatura e l'albero dei predecessori dipendono dall'ordine in cui si scorrono i successori.
1.8 In sintesi¶
In sintesi
-
Un grafo non orientato \(G=(V,E)\) ha spigoli \(\{u,v\}\), un grafo orientato \(G=(N,A)\) ha archi \((i,j)\); la somma dei gradi è \(2m\), quella dei gradi uscenti e quella dei gradi entranti è \(m\).
-
Le liste di adiacenza richiedono spazio \(n+m\); la matrice di incidenza nodo–arco ha \(+1\) nella coda e \(-1\) nella testa, e la riga \(i\) di \(\mat{B}\vet{x}\) è il flusso uscente meno il flusso entrante nel nodo \(i\).
-
Le componenti connesse e le componenti fortemente connesse sono classi di equivalenza; \(S(i)=R(i) \cap R'(i)\).
-
Un albero è connesso e aciclico, con \(n-1\) spigoli e un unico cammino fra ogni coppia di vertici; uno spigolo esterno a un albero ricoprente chiude un ciclo fondamentale.
-
\(\rank(\mat{B})=|N|-k\), e in un grafo connesso le basi di \(\mat{B}\) sono gli alberi ricoprenti.
-
La visita generica trova \(R(s)\) in tempo \(O(|N|+|A|)\); la BFS dà il numero minimo di archi.
Il grafo di riferimento in sintesi.
| nodi e archi | \(n=6\), \(m=9\) |
| componenti connesse | \(1\) |
| componenti fortemente connesse | \(\{1\}\), \(\{2,3,4,5\}\), \(\{6\}\) |
| \(\rank(\mat{B})\) | \(5\) |
| BFS da \(1\) | ordine \(1,2,3,4,5,6\); \(d=(0,1,1,2,2,3)\) |
| DFS da \(1\) | ordine \(1,2,4,3,5,6\) |
Esercizi su questo capitolo: Grafi