Vai al contenuto

1.6 Visita di un grafo

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

Input: un grafo orientato \(G=(N,A)\) dato dalle sue liste di adiacenza, una sorgente \(s \in N\)
Output: i nodi etichettati, uguali a \(R(s)\), e i predecessori \(\mathit{pred}(j)\)
1Passo 0 (inizializzazione). Etichettare \(s\) e porre \(\mathit{LIST}:=\{s\}\); tutti gli altri nodi non sono etichettati.
2Passo 1 (selezione). Se \(\mathit{LIST}=\emptyset\), STOP. Altrimenti selezionare un nodo \(i \in \mathit{LIST}\):
3 il primo nodo di \(\mathit{LIST}\) nella visita in ampiezza (BFS),
4 l'ultimo nodo di \(\mathit{LIST}\) nella visita in profondità (DFS).
5Passo 2 (etichettatura). Se \(i\) ha un arco ammissibile \((i,j)\), prendere il primo in \(L(i)\):
6 etichettare \(j\), porre \(\mathit{pred}(j):=i\) e aggiungere \(j\) in fondo a \(\mathit{LIST}\).
7 Altrimenti rimuovere \(i\) da \(\mathit{LIST}\). Andare al Passo 1.

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

  1. 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\).

  2. Letta all'indietro, è un cammino orientato da \(s\) a \(j\) lungo gli archi \((\mathit{pred}(h),h)\).

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

  1. Sia \(i_t\) il primo nodo non etichettato del cammino; \(t \ge 1\), perché \(s\) è etichettato.

  2. Il nodo \(i_{t-1}\) è etichettato, quindi è entrato in \(\mathit{LIST}\), e alla fine ne è uscito.

  3. 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\).

Figura 6

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.

  1. 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\).

  2. 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\).

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

Figura 7

  • 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