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. Su un albero preorder e postorder sono DFS; la BFS corrisponde alla visita per livelli, quella della numerazione a livelli degli heap (HeapAlbero binario completo e sua altezza floor(log2 n); heap = albero completo con heap-order property; proprietà (radice minima, cammini non decrescenti); rappresentazione su array con level numbering; insert con up-heap bubbling, removeMin con down-heap bubbling, rimozione di una entry qualsiasi; invarianti e costi Theta(log n); esempio svolto.Heap →). La differenza con gli alberi è che un grafo può avere cicli, quindi bisogna ricordare i vertici già visti (campo ID) per non girare all'infinito. 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. Le liste di livelli $L_i$ dell'algoritmo fanno da coda FIFO (Liste, pile e codeRipasso degli ADT elementari: lista index-based (array) e position-based (lista doppiamente concatenata con sentinelle), pila LIFO, coda FIFO, deque, iteratori; interfacce, implementazioni e costi; array estendibile e coda circolare.Liste, pile e code →): si esaminano i vertici nell'ordine in cui sono stati scoperti.
• 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. La ricorsione usa lo stack delle chiamate (Algoritmi ricorsiviAlgoritmi ricorsivi come induzione eseguita; albero della ricorsione e record di attivazione nello stack; esempi ReverseArray, LinearSum, Power in tempo logaritmico, Fibonacci ricorsivo (esponenziale) e con memoizzazione; analisi della complessità con l'albero della ricorsione e correttezza per induzione.Algoritmi ricorsivi →, Stack e chiamata di funzioni in ARMChiamata con BL e ritorno con BX LR; convenzione di chiamata AAPCS (argomenti in r0-r3, risultato in r0, registri da preservare r4-r11); stack discendente pieno con PUSH e POP; record di attivazione; funzioni foglia e non foglia; esempio ricorsivo del fattoriale con evoluzione dello stack.Stack e chiamata di funzioni in ARM →): è una pila LIFO, e per questo la DFS si può scrivere anche con una pila esplicita al posto della ricorsione. In un grafo molto profondo (un cammino di $10^6$ vertici) la ricorsione consuma $\Theta(n)$ di stack e in C può esaurirlo (Gestione della memoria in CSegmenti di memoria di un processo (codice, dati statici, stack, heap); durata delle variabili; allocazione dinamica con malloc, calloc, realloc e free; errori classici: memory leak, dangling pointer, double free, buffer overflow; strumenti di controllo.Gestione della memoria in C →).

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

Definizione (visita in ampiezza, 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).

Esempio. Sul grafo con liste $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$, la BFS da $1$ ha livelli $L_0=\{1\}$, $L_1=\{2,4\}$, $L_2=\{3,6\}$, $L_3=\{5,7\}$.

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à (BFS e spanning tree). 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$.

Esempio. Nello stesso grafo $d(1,6)=2$ (cammino $1,4,6$) e il BFS tree ha $n-1=6$ discovery edge.

Perché i livelli sono le distanze (per induzione sul livello: Principio di induzionePer dimostrare una proprietà per ogni n basta il passo base e il passo induttivo da n a n+1.Principio di induzione →). $L_0=\{s\}$ è a distanza $0$. Se i vertici di $L_i$ sono esattamente quelli a distanza $i$, i vertici scoperti scorrendo $L_i$ sono vicini di vertici a distanza $i$ non ancora visti: non possono essere a distanza $\le i$ (sarebbero già in un livello precedente), quindi sono a distanza $i+1$. E ogni vertice a distanza $i+1$ ha un vicino a distanza $i$, perciò viene scoperto. Per un cross edge $(u,v)$ con $u\in L_i$: alla fine dell'esame di $L_i$ il vertice $v$ è già visitato, quindi sta in un livello $\le i+1$; per simmetria $u$ sta in un livello $\le \text{liv}(v)+1$, e i livelli differiscono al più di $1$.

Traccia sul grafo dell'esempio (liste $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$), con $i$ il livello in esame:

Formula (complessità della BFS). 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)$. Il conto: ogni vertice di $C_s$ è estratto da una lista una volta e per ciascuno si percorre la sua lista di adiacenza, di lunghezza $\text{degree}(v)$ (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 →); il costo totale è $\sum_{v}\big(1+\text{degree}(v)\big)=n_s+2m_s$ perché la somma dei gradi è $2m_s$ (Grafi - definizioni e proprietàGrafo G=(V,E) diretto e non diretto, grafo semplice e pesato; incidenza, adiacenza, grado; cammini, cicli, sottografi, grafi connessi e componenti connesse; alberi liberi, foreste, spanning tree e spanning forest; proprietà con dimostrazioni (somma dei gradi = 2m, m <= n(n-1)/2, alberi m = n-1, connessi m >= n-1, foreste m <= n-1).Grafi - definizioni e proprietà →), e $n_s+2m_s\in\Theta(n_s+m_s)$. Con la matrice di adiacenza lo scorrimento dei vicini di ogni vertice costerebbe $\Theta(n)$ e il totale $\Theta(n^2)$.

Esempio. Con $n_s=7$ vertici e $m_s=9$ archi il costo è $\Theta(n_s+m_s)=\Theta(16)$.

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

Proprietà (DFS). 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. La DFS da $1$ nello stesso grafo visita $1,2,3,5,6,4,7$ con $6$ discovery edge e $3$ back edge, $(3,6)$, $(1,4)$ e $(2,4)$.

Traccia (la pila delle chiamate cresce a ogni discovery edge e si accorcia ai ritorni): da $1$ si scende a $2$ (primo vicino non visitato), da $2$ a $3$, da $3$ a $5$, da $5$ a $6$. In $6$, con lista $3,4,5,7$: l'arco $(6,3)$ non è etichettato ma $3$ è già visitato, quindi è un back edge; $4$ non è visitato, discovery edge $(6,4)$ e si scende in $4$, dove $(4,1)$ e $(4,2)$ portano a vertici già visitati: back edge $(1,4)$ e $(2,4)$. Si torna in $6$: l'arco $(6,5)$ è già etichettato (è il discovery edge $(5,6)$ visto da $5$); $7$ non è visitato, discovery edge $(6,7)$. Nessun vertice è visitato due volte, perché l'ID lo impedisce.

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 $4$ come nel cammino dell'albero DFS $1, 2, 3, 5, 6$ (quattro archi): 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

Proprietà (confronto tra BFS e DFS)

	BFS	DFS
struttura di appoggio	liste di livelli (coda)	ricorsione (pila)
archi non-tree	cross edge, tra livelli adiacenti	back edge
cammini nell'albero	minimi in numero di archi	non necessariamente minimi
costo (liste di adiacenza)	$\Theta(n + m)$	$\Theta(n + m)$

Esempio. La BFS trova $d(1,6)=2$, mentre il cammino da $1$ a $6$ nell'albero DFS ($1,2,3,5,6$) ha lunghezza $4$.

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 →). Nelle reti di calcolatori la BFS è l'idea dell'instradamento con il minimo numero di salti (Algoritmi di instradamento - link state e distance vectorL'instradamento (routing) trova il percorso di costo minimo in un grafo pesato in cui i router sono nodi e le reti tra due router sono archi. Link state: ogni router diffonde con un flooding i pacchetti LSP sui propri collegamenti, ricostruisce tutto il grafo e applica Dijkstra (nodi con stato (distanza, permanente o temporaneo)). Distance vector: ogni router conosce solo i vicini e scambia con loro il proprio vettore delle distanze, aggiornato con Bellman-Ford $D_{A,w}=\min{D_{A,w},,D_{A,Y}+d_{Y,w}}$; converge in al più $n-1$ giri ma può soffrire del conteggio all'infinito (limite a 16, hold down, aggiornamenti immediati, split horizon con poison reverse). Path vector: ogni annuncio porta l'intero cammino, si sceglie per politica e non per costo, e i cicli si scoprono trovando sé stessi nel cammino. Dijkstra è corretto se i costi sono non negativi (invariante: un nodo permanente ha già la distanza vera); Bellman-Ford è corretto perché dopo $k$ giri conosce i cammini minimi con al più $k+1$ archi.Algoritmi di instradamento - link state e distance vector →); nella DFS la stessa struttura "vai avanti finché puoi, poi torna indietro" è il backtracking della ricorsione (RicorsioneFunzioni che chiamano se stesse: caso base e passo ricorsivo, stack delle chiamate, esempi su numeri, stringhe e liste, ricorsione multipla e suo costo, divide et impera, confronto con l'iterazione.Ricorsione →).

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.