Grafi e alberi: visite BFS e DFS per l'esame di algoritmi

Se segui Algoritmi e strutture dati (informatica o ingegneria), le lezioni sono partite da qualche settimana e di solito è il periodo in cui dopo la complessità arrivano grafi e alberi. L’esame della sessione invernale, tra gennaio e febbraio, cade fra otto e dieci settimane: hai tempo per costruire il metodo con calma. Questo argomento ha un vantaggio: le tracce a mano si imparano a fare, e all’esame sono quasi sempre il modo più sicuro di prendere punti. Prima di questo post conviene avere chiara la complessità con la notazione O-grande; per la rappresentazione in memoria con nodi e riferimenti ti servono anche i puntatori in C.

Rappresentare un grafo

Un grafo $G=(V,E)$ ha un insieme di nodi (vertici) $V$ e uno di archi $E$. Useremo $V$ e $E$ anche per i loro numeri, come nei costi. Due rappresentazioni standard:

• Liste di adiacenza: per ogni nodo, la lista dei suoi vicini. Occupa spazio $O(V+E)$ ed è la scelta naturale per grafi radi.
• Matrice di adiacenza: una tabella $V\times V$ con 1 (o il peso) se esiste l’arco. Occupa $O(V^2)$ e permette di sapere in tempo costante se due nodi sono collegati.

In un grafo non orientato ogni arco compare due volte (in due liste, in due celle simmetriche): la somma dei gradi è $2E$.

Il grafo di tutto l’articolo ha 6 nodi $A,\dots ,F$ e 6 archi: $A-B$, $A-C$, $B-D$, $C-D$, $C-E$, $E-F$. Liste di adiacenza, in ordine alfabetico:

I gradi sono 2, 2, 3, 2, 2, 1: sommano a 12, cioè $2E$ con $E=6$.

BFS: visita in ampiezza con la coda

Si parte da una sorgente, la si marca e la si mette in coda. Finché la coda non è vuota: si estrae il primo nodo e si mettono in coda i suoi vicini non ancora marcati, marcandoli subito.

BFS(G, s):
    marca s; coda = [s]
    finché coda non è vuota:
        u = estrai(coda)
        visita u
        per ogni v in adiacenti(u):
            se v non è marcato:
                marca v; inserisci v in coda

Traccia da $A$:

1. Estraggo $A$: inserisco $B,C$. Coda: $[B,C]$.
2. Estraggo $B$: $A$ è marcato, inserisco $D$. Coda: $[C,D]$.
3. Estraggo $C$: $A$ e $D$ già marcati, inserisco $E$. Coda: $[D,E]$.
4. Estraggo $D$: i vicini $B,C$ sono già marcati. Coda: $[E]$.
5. Estraggo $E$: inserisco $F$. Coda: $[F]$.
6. Estraggo $F$. Coda vuota.

Ordine di visita BFS: $A,B,C,D,E,F$. Il livello a cui scopro un nodo è la distanza minima in archi: $A=0$, $B=C=1$, $D=E=2$, $F=3$. Per questo la BFS trova i cammini minimi nei grafi non pesati.

DFS: visita in profondità con ricorsione

Si va avanti sul primo vicino non visitato e si torna indietro solo quando i vicini sono finiti.

DFS(u):
    marca u; visita u
    per ogni v in adiacenti(u):
        se v non è marcato:
            DFS(v)

Traccia da $A$: parto da $A$ e vado in $B$; da $B$ il vicino $A$ è marcato, quindi vado in $D$; da $D$, $B$ è marcato, vado in $C$; da $C$, $A$ e $D$ sono marcati, vado in $E$; da $E$ vado in $F$. Da $F$ non c’è altro e torno indietro fino ad $A$.

Ordine di visita DFS: $A,B,D,C,E,F$. Rispetto alla BFS cambia: $D$ viene prima di $C$, perché la DFS si addentra prima di tornare. La pila delle chiamate ricorsive fa il lavoro che nella BFS fa la coda. Se scrivi la DFS iterativa con una pila esplicita, attenzione all’ordine: se inserisci i vicini in ordine alfabetico, il primo estratto è l’ultimo, quindi l’ordine di visita si inverte rispetto a quello ricorsivo, a meno di inserirli al contrario.

Complessità: O(V+E)

Con le liste di adiacenza, in entrambe le visite ogni nodo viene marcato e processato una volta (costo $V$) e ogni lista viene scorsa una volta; le liste hanno in tutto $2E$ elementi per un grafo non orientato, $E$ per uno orientato. Il costo è

Con la matrice di adiacenza, per trovare i vicini di un nodo bisogna scorrere un’intera riga di $V$ celle: per $V$ nodi il costo diventa $O(V^2)$. Su grafi radi le liste vincono.

Alberi binari: pre-, in- e post-ordine

Un albero è un grafo connesso e senza cicli; l’albero binario ha per ogni nodo al più un figlio sinistro e uno destro. Le visite sono una DFS con tre varianti, secondo il momento in cui visiti la radice:

• pre-ordine: radice, sottoalbero sinistro, sottoalbero destro;
• in-ordine: sinistro, radice, destro;
• post-ordine: sinistro, destro, radice.

Prendiamo l’albero con radice 8, figli di 8: 3 e 10; figli di 3: 1 e 6; figli di 6: 4 e 7; 10 ha solo il figlio destro 14, e 14 ha il solo figlio sinistro 13.

• Pre-ordine: $8,3,1,6,4,7,10,14,13$
• In-ordine: $1,3,4,6,7,8,10,13,14$
• Post-ordine: $1,4,7,6,3,13,14,10,8$
• Per livelli (la BFS sull’albero): $8,3,10,1,6,14,4,7,13$

In questo albero valgono le regole dell’albero binario di ricerca (a sinistra i minori, a destra i maggiori), perciò l’in-ordine esce ordinato. È un’osservazione da esame, ma vale solo per quel tipo di albero.

Gli errori tipici all’esame

Ordine dei vicini. L’ordine di visita dipende dall’ordine con cui sono scritte le liste di adiacenza. Se il testo non lo dice, dichiaralo (“vicini in ordine alfabetico”): con le liste invertite, sul nostro grafo la BFS darebbe $A,C,B,E,D,F$ e la DFS $A,C,E,F,D,B$. Una risposta diversa dalla soluzione può comunque essere corretta, se dichiari la convenzione.

Nodi già visitati. Dimenticare il marcamento significa tornare su nodi già visti e, se c’è un ciclo, non terminare. Un’altra variante: nella BFS marchi il nodo quando lo estrai e non quando lo inserisci, e così lo puoi mettere in coda più volte.

Confondere coda e pila. BFS con la pila non è una BFS.

Pre-, in- e post-ordine. Scrivere la sequenza dalla definizione, partendo dalla radice e scendendo ricorsivamente, non per intuizione.

Costo. Dire $O(V^2)$ per le liste, o $O(E)$ senza il $V$: in un grafo non connesso o con nodi isolati il termine $V$ non si può tralasciare.

Tre esercizi svolti

1. Cammino minimo con la BFS

Qual è il numero minimo di archi per andare da $A$ a $F$ nel grafo sopra? Dai un cammino.

Dalla traccia BFS: $F$ è scoperto da $E$ a livello 3, $E$ da $C$ a livello 2, $C$ da $A$ a livello 1. Cammino $A\to C\to E\to F$, 3 archi. Non esiste un cammino più corto: per arrivare a $F$ bisogna passare da $E$, unico vicino di $F$, e $E$ è raggiungibile solo da $C$, che dista 1 da $A$.

2. Liste o matrice?

Confronta lo spazio per il grafo di 6 nodi e 6 archi, e per un grafo con 1000 nodi e 3000 archi.

Per il nostro grafo la matrice ha $6\cdot 6=36$ celle, le liste $2E=12$ elementi (più 6 teste). Con $V=1000$ e $E=3000$: la matrice ha $1000000$ celle, le liste circa $6000$ elementi (più 1000 teste). Il grafo è molto rado, e infatti le liste costano una piccola frazione. Per una visita, il confronto è $O(V+E)=O(4000)$ contro $O(V^2)=O(1000000)$.

3. Alberi: ricostruire dalla coppia di visite

Pre-ordine $A,B,D,E,C$; in-ordine $D,B,E,A,C$. Ricostruisci l’albero e scrivi il post-ordine.

La radice è il primo del pre-ordine: $A$. Nell’in-ordine, $D,B,E$ stanno a sinistra di $A$ e $C$ a destra. Il sottoalbero sinistro ha pre-ordine $B,D,E$: radice $B$; nell’in-ordine $D$ è a sinistra di $B$ e $E$ a destra. Quindi $A$ ha come figli $B$ (con figli $D$ e $E$) e $C$. Post-ordine: $D,E,B,C,A$.

Metti alla prova

Per grafi e alberi è utile la pagina delle simulazioni per l’università, che raccoglie i quesiti per corso: controlla quanto copre di Algoritmi, perché la copertura dipende dal corso. L’esercizio più utile resta rifare le tracce a mano su un grafo tuo, cambiando sorgente e ordine dei vicini. Anche lo studio di mappe di Karnaugh e algebra di Boole è un argomento di Fondamenti dove la traccia a mano paga allo stesso modo. Altre risorse sono nella pagina informatica; per un confronto 1-a-1 online sulle tracce, puoi partire da una diagnosi gratuita.