Visite di grafi - BFS e DFS

Una visita (traversal) è un'esplorazione sistematica di $G = (V, E)$ a partire da un vertice $s$. Come per gli alberi (vedi Visite di alberiVisite in preorder e postorder come schemi generali (template) da adattare; complessità Theta(n + somma dei costi di visita) perché la somma dei figli è n-1; esempi (indice di un libro, spazio occupato in un file system); profondità con il preorder, altezza con il postorder; antenato comune più basso.Visite di alberi →) sono schemi generali (design pattern) in cui l'operazione di "visita" si adatta al problema. Una scansione semplice di $L_V$ e $L_E$ tocca tutto ma senza seguire la struttura del grafo, e serve a poco (vedi Rappresentazione dei grafiStrutture di base (lista dei vertici LV, lista degli archi LE), liste di adiacenza, matrice di adiacenza; operazioni incidentEdges, opposite, areAdjacent; spazio e tempi a confronto; esempio con un grafo di 5 vertici.Rappresentazione dei grafi →).

• BFS (breadth-first search, in ampiezza): visitato un vertice, si visitano tutti i suoi vicini prima dei vicini dei vicini.
• DFS (depth-first search, in profondità): visitato un vertice, si visita un vicino, poi un vicino del vicino, e così via, tornando indietro quando non ci sono nuovi vertici.

Convenzioni: ogni vertice $v$ ha un campo v.ID ($0$ = non visitato, $\ge 1$ = visitato); ogni arco $e$ ha e.label (null = non etichettato). incidentEdges(v) restituisce un iteratore agli archi incidenti su $v$ (la lista di adiacenza) e opposite(v, e) il vertice di $e$ diverso da $v$, entrambi in $\Theta(1)$ per elemento. Prima di una visita tutti i vertici hanno ID $= 0$ e tutti gli archi sono non etichettati.

BFS

La BFS da $s$ visita la componente connessa $C_s$ di $s$, etichetta gli archi di $C_s$ come DISCOVERY EDGE o CROSS EDGE e divide i vertici in livelli $L_i$ secondo la distanza $i$ da $s$ (distanza $d(x, y)$ = lunghezza minima di un cammino; $+\infty$ se in componenti diverse).

Algoritmo BFS(G, s)
visita s; s.ID <- 1
L0 <- lista con s; i <- 0
while Li non è vuota do
    Li+1 <- lista vuota
    forall v in Li do
        forall e in G.incidentEdges(v) do
            if e.label = null then
                w <- G.opposite(v, e)
                if w.ID = 0 then
                    e.label <- DISCOVERY EDGE
                    visita w; w.ID <- 1; inserisci w in Li+1
                else e.label <- CROSS EDGE
    i <- i + 1

Proprietà. Dopo BFS(G, s): tutti i vertici di $C_s$ sono visitati e tutti i suoi archi etichettati; i discovery edge formano uno spanning tree di $C_s$ radicato in $s$ (il BFS tree); per ogni $v \in L_i$ il cammino nel BFS tree da $s$ a $v$ ha $i = d(s, v)$ archi; se $(u, v)$ è un cross edge i livelli di $u$ e $v$ differiscono al più di $1$.

Complessità. Ogni vertice di $C_s$ entra in una lista una sola volta (poi ID $\ne 0$) e ogni arco di $C_s$ viene etichettato una volta; dalla lista di adiacenza di ciascun vertice ogni arco è esaminato due volte (una per estremo). Con $n_s$ vertici e $m_s$ archi in $C_s$ il costo è $\Theta(n_s + m_s) = \Theta(m_s)$ (se $s$ non è isolato, $m_s \ge n_s - 1$). Se $G$ è connesso, $\Theta(n + m)$.

Per visitare tutto il grafo anche se non connesso:

forall v in V do v.ID <- 0
forall v in V do
    if v.ID = 0 then BFS(G, v)

DFS

Algoritmo DFS(G, v)          (prima invocazione: v = s)
visita v; v.ID <- 1
forall e in G.incidentEdges(v) do
    if e.label = null then
        w <- G.opposite(v, e)
        if w.ID = 0 then
            e.label <- DISCOVERY EDGE
            DFS(G, w)
        else e.label <- BACK EDGE

Dopo DFS(G, s): tutti i vertici di $C_s$ sono visitati, tutti gli archi di $C_s$ sono etichettati DISCOVERY o BACK, e i discovery edge formano uno spanning tree di $C_s$ radicato in $s$. Complessità $\Theta(m_s)$ con liste di adiacenza ($\Theta(n + m)$ se connesso), con lo stesso argomento della BFS. Un vertice $u$ si dice discoverable da $v$ se esiste un cammino da $v$ a $u$ fatto di vertici non ancora visitati.

Esempio svolto

Grafo con vertici $1..7$ e liste di adiacenza in ordine crescente: $1: 2, 4$; $2: 1, 3, 4$; $3: 2, 5, 6$; $4: 1, 2, 6$; $5: 3, 6$; $6: 3, 4, 5, 7$; $7: 6$.

• DFS da 1: ordine di visita $1, 2, 3, 5, 6, 4, 7$. Discovery edge: $(1,2), (2,3), (3,5), (5,6), (6,4), (6,7)$ (da $6$ si va in $4$, poi si torna e si scopre $7$). Back edge: $(3,6)$, $(1,4)$, $(2,4)$.
• BFS da 1: ordine $1, 2, 4, 3, 6, 5, 7$; livelli $L_0 = \{1\}$, $L_1 = \{2, 4\}$, $L_2 = \{3, 6\}$, $L_3 = \{5, 7\}$. Discovery edge: $(1,2), (1,4), (2,3), (4,6), (3,5), (6,7)$. Cross edge: $(2,4)$, $(3,6)$, $(5,6)$. In effetti $d(1, 6) = 2$ (tramite $4$) e non $3$ come nel cammino dell'albero DFS $1, 2, 3, 5, 6$: la BFS dà le distanze minime, la DFS no.

(Tracce verificate eseguendo le implementazioni.) Un secondo esempio d'esame: liste $A: B,C,D$; $B: A,E,F$; $C: A,G$; $D: A,H$; $E: B$; $F: B,I$; $G: C$; $H: D,I$; $I: F,H$. La BFS da $A$ visita $A, B, C, D, E, F, G, H, I$ (livello 1: $B, C, D$; livello 2: $E, F, G, H$; livello 3: $I$).

Applicazioni (tutte in $O(n + m)$)

Adattare la BFS (domande d'esame ricorrenti):

• vertici a distanza $\le d$ da $s$: si esegue la BFS fermandosi quando $i = d$ (non si costruisce $L_{d+1}$) e si contano i vertici dei livelli $L_0, \dots, L_d$; costo $O(n + m)$;
• numero di vertici raggiungibili da $s$ e distanza massima: si conta il numero di vertici inseriti in lista e si restituisce $i$ dell'ultimo livello non vuoto;
• dimensione di ogni componente: una BFS che restituisce il contatore dei vertici scoperti (vedi l'Esercizio 23 · escursioni e componenti connesse).

BFS contro DFS

Per grafi pesati i cammini minimi richiedono l'algoritmo di Dijkstra, che generalizza la BFS (vedi Cammini minimi e algoritmo di DijkstraGrafi pesati, lunghezza di un cammino e distanza; sottocammini di un cammino minimo; problema SSSP; algoritmo di Dijkstra con cloud e priority queue, rilassamento degli archi, esempio svolto; correttezza (due lemmi) e complessità O(min(n^2, (n+m) log n)) con lista non ordinata o heap; pesi non negativi.Cammini minimi e algoritmo di Dijkstra →).

Errori comuni

• Controllare ID ma non label: ogni arco verrebbe esaminato due volte e l'etichettatura non sarebbe consistente.
• Dimenticare di rilanciare la visita dai vertici non visitati: si visita solo la componente di $s$.
• Dire che la BFS costa $\Theta(n)$ o la DFS $\Theta(m)$: il costo è $\Theta(n + m)$ (liste di adiacenza); con la matrice sarebbe $\Theta(n^2)$.
• Usare la DFS per cammini minimi in numero di archi.