Vai al contenuto

1.6 Ricerca su grafi

Parte 1 · Grafi · Capitolo 1 · Capitolo 1: Grafi · Dispensa, volume 1 (PDF) · Esercizi: Grafi · App: Ricerca su grafo: BFS e DFS

Definizione 1.24: ricerca grafo

Dato un grafo diretto \(G=(N,A)\) e un nodo \(s \in N\), source, una graph search trova l'insieme \(R(s)\) dei nodi raggiungibili da \(s\). Durante la ricerca:

  • un nodo è etichettato quando la ricerca lo raggiunge e rimane 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 vengono mantenuti in una lista, \(\mathit{LIST}\);

  • un arco \((i,j)\) è ammissibile se \(i\) è etichettato e \(j\) non lo è.

Algoritmo: Ricerca generica nel grafo

Input: un grafo diretto \(G=(N,A)\) dato dalle sue liste di adiacenza, una fonte \(s \in N\)
Output: i nodi etichettati, uguali a \(R(s)\), e i predecessori \(\mathit{pred}(j)\)
1Passaggio 0 (inizializzazione). Etichetta \(s\) e imposta \(\mathit{LIST}:=\{s\}\); tutti gli altri nodi non sono etichettati.
2Passaggio 1 (selezione). Se \(\mathit{LIST}=\emptyset\), STOP. Altrimenti seleziona un nodo \(i \in \mathit{LIST}\):
3 il nodo primo di \(\mathit{LIST}\) nella ricerca in ampiezza (BFS),
4 il nodo ultimo di \(\mathit{LIST}\) nella ricerca approfondita (DFS).
5Passaggio 2 (etichettatura). Se \(i\) ha un arco ammissibile \((i,j)\), prendi il primo in \(L(i)\):
6 etichetta \(j\), imposta \(\mathit{pred}(j):=i\) e aggiungi \(j\) alla fine di \(\mathit{LIST}\).
7 Altrimenti rimuovere \(i\) da \(\mathit{LIST}\). Vai al passaggio 1.

  • Nel BFS la lista \(\mathit{LIST}\) è una queue (first in, first out): i nodi vengono elaborati nell'ordine in cui sono etichettati.

  • Nel DFS la lista \(\mathit{LIST}\) è un stack (last in, first out): la ricerca parte sempre dal più nodo recentemente etichettato ancora in \(\mathit{LIST}\) e torna indietro solo quando quel nodo non ha archi ammissibili.

  • L'ordine degli elenchi di adiacenza decide quale arco ammissibile viene preso per primo; con elenchi ordinati in ordine crescente indice, come in questo modulo, il risultato è unico.

1.6.1 L'albero predecessore

Proposizione 1.25: albero predecessore

Ad ogni iterazione, gli archi \((\mathit{pred}(j),j)\), per i nodi etichettati \(j \neq s\), formano un albero sui nodi etichettati, albero predecessore. Per ogni nodo etichettato \(j\) contiene un percorso diretto 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\). A partire da \(j\) e passando a predecessore, i nodi sono etichettati sempre prima, quindi la sequenza termina con \(s\).

  2. Letto al contrario, è un percorso diretto da \(s\) a \(j\) lungo gli archi \((\mathit{pred}(h),h)\).

  3. Quindi gli archi \(r-1\) collegano i nodi etichettati \(r\) e formano un albero per Teorema 1.17(b). □

Teorema 1.26: correttezza della ricerca

Al termine della ricerca generica, BFS e DFS inclusi, i nodi etichettati sono esattamente i nodi di \(R(s)\).

Dimostrazione

Ogni nodo etichettato è raggiungibile da \(s\), da Proposizione 1.25. Viceversa, lasciamo \(j \in R(s)\) e lascia che \(s=i_0,i_1,\dots,i_k=j\) sia un percorso diretto; presupponiamo per assurdo che \(j\) non sia etichettato.

  1. Sia \(i_t\) il primo nodo senza etichetta del percorso; \(t \ge 1\), poiché \(s\) è etichettato.

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

  3. Un nodo esce da \(\mathit{LIST}\) solo quando non ha arco ammissibile. Ma \((i_{t-1},i_t)\) è ammissibile fino alla fine, perché le etichette non si tolgono mai: un controsenso. □

Teorema 1.27: tempo di esecuzione della ricerca

Con gli elenchi di adiacenza, la ricerca generica viene eseguita nel tempo \(O(|N|+|A|)\).

Dimostrazione

Ogni nodo mantiene un puntatore alla posizione corrente nella sua lista \(L(i)\); il puntatore si sposta in avanti oltre l'etica successori e non torna mai indietro, poiché le etichette non vengono mai rimosse.

  • Ogni iterazione etichetta un nodo o rimuove un nodo da \(\mathit{LIST}\). Ogni nodo viene etichettato al massimo una volta e rimosso a più una volta, quindi ci sono al massimo \(2n\) iterazioni, ciascuna con \(O(1)\) che funziona oltre al puntatore.

  • Il puntatore del nodo \(i\) si sposta al massimo \(\deg^+(i)\) volte in totale 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 scansionando una riga di lunghezza \(n\), e la ricerca richiede tempo \(O(n^2)\).

1.6.2 La visita in ampiezza sul grafo di riferimento

Esempio 1.9: BFS dal nodo \(1\)

Eseguiamo il BFS sul grafo di riferimento da \(s=1\), con gli elenchi di adiacenza di Esempio 1.5. Ogni riga rappresenta un'iterazione e dopo di essa viene visualizzato \(\mathit{LIST}\):

iterazione e \(i\) selezionato e 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\) (vuoto)

L'ordine di etichettatura è \(1,2,3,4,5,6\): ogni nodo è raggiungibile da \(1\). L'albero precedente ha gli archi \((1,2)\), \((1,3)\), \((2,4)\), \((3,5)\), \((4,6)\); è lo albero ricoprente di Esempio 1.7. Accanto a ciascuno nodo, in figura è riportato il numero \(d(j)\) di archi del percorso dell'albero da \(1\) a \(j\).

Figura 6

Proposizione 1.28: BFS trova i percorsi più brevi in numero di archi

Nell'albero precedente del BFS, lasciare \(d(s)=0\) e \(d(j)=d(\mathit{pred}(j))+1\) per ogni \(j \neq s\) etichettato. Quindi, per ogni \(j \in R(s)\), \(d(j)\) è il numero minimo di archi di un percorso diretto 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 a Passaggio 0. Un nuovo nodo \(j\) viene etichettato da \(u_1\) e aggiunto con \(d(j)=d(u_1)+1\); rimuovendo \(u_1\) si 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\) lasci \(\mathit{LIST}\), da un nodo \(u\) nella parte anteriore di \(\mathit{LIST}\), etichettato non più tardi di \(i\): \(d(j)=d(u)+1 \le d(i)+1\). If \(j\) is labelled before \(i\), then \(d(j) \le d(i)\) di fatto 2.

Sia \(s=i_0,i_1,\dots,i_k=j\) un percorso diretto con il numero minimo \(k\) di archi. I suoi nodi sono etichettati (Teorema 1.26), e di fatto 3, \(d(j) \le d(i_{k-1})+1 \le \dots \le d(s)+k=k\). L'albero il percorso da \(s\) a \(j\) è un percorso diretto con archi \(d(j)\), quindi \(d(j) \ge k\). □

  • In Esempio 1.9, i valori \(d=(0,1,1,2,2,3)\) sono il numero minimo di archi dal nodo \(1\): ad esempio, i percorsi diretti più brevi al nodo \(6\) hanno archi \(3\), come \(1,2,4,6\).

1.6.3 La ricerca approfondita sul grafo di riferimento

Esempio 1.10: DFS dal nodo \(1\)

Eseguiamo il DFS sul grafo di riferimento da \(s=1\): il nodo selezionato è sempre l'ultimo di \(\mathit{LIST}\).

iterazione e \(i\) selezionato e 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) (vuoto)

L'ordine di etichettatura è \(1,2,4,3,5,6\) e l'albero precedente ha gli archi \((1,2)\), \((2,4)\), \((4,3)\), \((3,5)\), \((5,6)\): un unico percorso diretto. Accanto a ciascun nodo, la figura mostra la sua posizione \(o(j)\) nell'ordine di etichettatura.

Figura 7

  • Entrambe le ricerche etichettano tutti i nodi, come garantisce Teorema 1.26, ma i loro alberi differire. L'albero DFS raggiunge il nodo \(6\) con archi \(5\), mentre l'albero BFS utilizza \(3\).

1.6.4 Utilizzo della ricerca

  • Componenti connessi. In un grafo non orientato, una ricerca da un vertice senza etichetta ne etichetta l'intero componente; ripetendolo da ogni vertice ancora non etichettato si trovano tutti i componenti in tempo \(O(n+m)\).

  • Componenti fortemente connessi. Una ricerca in \(G\) e una nel grafo invertito \(G'\) restituiscono \(R(i)\) e \(R'(i)\), quindi \(S(i)=R(i) \cap R'(i)\); ripeterlo per un nodo di ogni componente ancora sconosciuto richiede \(O(n(n+m))\) ora.

  • Spanning tree. Su un grafo connesso non orientato, l'albero predecessore di una ricerca da qualsiasi vertice è un albero di copertura.

Una ricerca sul grafo etichetta esattamente i nodi raggiungibili dalla sorgente, in tempo \(O(|N|+|A|)\), e i suoi predecessori formano un albero. Il BFS (una coda) fornisce percorsi con il numero minimo di archi; il DFS (uno stack) va prima in profondità.

1.7 Errori tipici

Attenzione

  • Scambio dei segni della matrice di incidenza. La voce è \(+1\) in coda e \(-1\) in testa: il la colonna di \((4,3)\) ha \(+1\) nella riga \(4\).

  • Chiamare una passeggiata un percorso. Un percorso ha vertici distinti; una passeggiata può ripeterli e contiene sempre a percorso con gli stessi punti finali.

  • Confusione tra connettività debole e forte. Il grafo di riferimento è debolmente connesso, ma ha tre componenti fortemente connessi.

  • Conteggio solo degli lati. Un grafo con lati \(n-1\) non deve essere un albero: deve anche essere connesso, oppure aciclico.

  • Credere che la matrice di incidenza abbia rango di riga completo. Il suo rango è \(|N|-k\): in un grafo connesso uno la riga è sempre ridondante.

  • Percorsi più brevi previsti dal DFS. Solo l'albero BFS fornisce il numero minimo di archi e solo quando ogni arco conta uno.

  • Dimenticare l'ordine degli elenchi. L'ordine di etichettatura e l'albero precedente dipendono dall'ordine in cui vengono scansionati i successori.

1.8 In sintesi

In sintesi

  • Un grafo non orientato \(G=(V,E)\) ha archi \(\{u,v\}\), un grafo diretto \(G=(N,A)\) ha archi \((i,j)\); i gradi sommare a \(2m\), i gradi in uscita e in entrata a \(m\).

  • Le liste di adiacenza necessitano di spazio \(n+m\); la matrice di incidenza nodo-arco ha \(+1\) in coda e \(-1\) in testa, e la riga \(i\) di \(\mat{B}\vet{x}\) è il deflusso meno l'afflusso del nodo \(i\).

  • Le componenti connesse e fortemente connesse sono classi di equivalenza; \(S(i)=R(i) \cap R'(i)\).

  • Un albero è connesso e aciclico, con lati \(n-1\) e un percorso unico tra ogni due vertici; un lato esterno uno albero ricoprente chiude un ciclo fondamentale.

  • \(\rank(\mat{B})=|N|-k\), e in un grafo connesso le basi di \(\mat{B}\) sono gli albero ricoprente.

  • La ricerca generica trova \(R(s)\) nel tempo \(O(|N|+|A|)\); il BFS fornisce il numero minimo di archi.

Il grafo di riferimento in sintesi.

nodi e archi \(n=6\), \(m=9\)
componenti collegati \(1\)
componenti fortemente collegati \(\{1\}\), \(\{2,3,4,5\}\), \(\{6\}\)
\(\rank(\mat{B})\) \(5\)
BFS da \(1\) e ordina \(1,2,3,4,5,6\); \(d=(0,1,1,2,2,3)\)
DFS da \(1\) e ordina \(1,2,4,3,5,6\)

Esercizi su questo capitolo: Grafi