Cosa sono gli algoritmi BFS e DFS e quando scegliere ciascuno?

BFS e DFS sono algoritmi di attraversamento di grafi che individuano sistematicamente i vertici raggiungibili da un vertice iniziale. La BFS si espande livello per livello a partire dai vertici più vicini, risultando adatta quando serve un percorso con il numero minimo di archi in un grafo non pesato. La DFS segue un ramo il più lontano possibile prima di tornare indietro, perciò viene usata come base per problemi quali l'analisi strutturale, il rilevamento dei cicli e l'ordinamento topologico. Nessuno dei due è sempre migliore: la scelta dipende dal criterio relativo al percorso e dallo scopo del grafo. ocw.mit.edu↗algs4.cs.princeton.edu↗

Cosa trovano BFS e DFS nell'attraversamento di un grafo?

Un grafo è una struttura relazionale composta da vertici e archi. I vertici rappresentano entità come persone, città, pagine web o attività, mentre gli archi rappresentano le connessioni tra esse, come amicizie, strade, link o relazioni di propedeuticità. L'insieme dei vertici è indicato con $V$, mentre l'insieme degli archi con $E$.

Se gli archi non hanno una direzione, il grafo è non orientato. Per esempio, un'amicizia reciproca può di solito essere considerata bidirezionale. Al contrario, relazioni come A che segue B o l'attività A che deve terminare prima dell'attività B formano un grafo orientato. In un grafo orientato, è possibile percorrere un arco solo nella direzione della freccia; non ci si può spostare automaticamente nella direzione opposta. ocw.mit.edu↗

La domanda più basilare nell'attraversamento di un grafo è: «Quali vertici sono raggiungibili da un punto iniziale $s$?». Nel rispondere a questa domanda, BFS e DFS possono anche registrare informazioni aggiuntive, ad esempio se un vertice è stato visitato, il percorso con cui ogni vertice è stato raggiunto per la prima volta e l'ordine di attraversamento. Tuttavia, un attraversamento avviato da un vertice elabora solo la porzione effettivamente raggiungibile da quel vertice. Non visita necessariamente tutti i vertici del grafo. ocw.mit.edu↗

Anche un albero è un tipo di grafo. Pertanto, BFS e DFS possono essere utilizzati per problemi che hanno l'aspetto di alberi, come gerarchie di cartelle o organigrammi. Tuttavia, è importante ricordare che un grafo generale può contenere cicli che riportano a un vertice e percorsi multipli verso lo stesso vertice. Applicare direttamente a un grafo generale un'implementazione progettata soltanto per l'attraversamento degli alberi può causare visite duplicate.

Come esplora per primi i vertici vicini la BFS?

BFS significa Breadth-First Search, ovvero ricerca in ampiezza. Individua prima i vertici raggiungibili dal punto iniziale con un arco, poi quelli che richiedono due archi, poi tre, espandendo l'intervallo di ricerca in questo ordine. Qui la distanza non è una distanza fisica né un costo: è il numero di archi da percorrere a partire dal punto iniziale. algs4.cs.princeton.edu↗

A questo scopo, la BFS usa di solito una coda. Una coda è una struttura dati FIFO (First In, First Out), cioè il primo elemento inserito è il primo a essere rimosso. Inserisci il vertice iniziale nella coda e contrassegnalo come visitato, quindi rimuovi un vertice dalla parte anteriore della coda. Contrassegna come visitati tutti i vicini non ancora scoperti di quel vertice e aggiungili in fondo alla coda. Ripeti finché la coda è vuota. Poiché i vertici vicini scoperti in precedenza vengono elaborati per primi, viene preservata l'espansione livello per livello. gh.cp-algorithms.com↗algs4.cs.princeton.edu↗

Per esempio, supponi che, partendo da A, tu scopra i vicini B e C di A. Quando la BFS elabora B, scopre i vicini di B; poi elabora C e scopre i vicini di C. Anche se un vertice scoperto da B è più profondo, C, che era già stato inserito nella coda allo stesso livello, viene elaborato prima o subito dopo. L'ordine esatto tra B e C può variare in base all'ordine in cui i vertici adiacenti sono memorizzati.

L'aspetto essenziale della BFS è contrassegnare un vertice come visitato non appena viene scoperto. Se rimandi il contrassegno fino alla sua rimozione dalla coda, due vertici possono scoprire entrambi lo stesso vicino e inserirlo nella coda più di una volta. In una BFS tipica, contrassegnare un nuovo vicino come scoperto nell'esatto momento in cui viene aggiunto alla coda è più semplice e sicuro.

In quali condizioni la BFS fornisce un percorso più breve?

La BFS viene spesso scelta perché, in un grafo non pesato, trova un percorso con il numero minimo di archi dal vertice iniziale a ogni vertice raggiungibile. Esamina tutti i vertici a un passo dalla partenza prima di esaminare quelli a due passi, quindi non può comparire in seguito un percorso con meno archi di quello che scopre per la prima volta un vertice. Se registri il vertice precedente come padre quando ciascun vertice viene scoperto per la prima volta durante la BFS, tali puntatori al padre formano un albero dei percorsi minimi. algs4.cs.princeton.edu↗

Per ricostruire un percorso, segui a ritroso i puntatori al padre dal vertice di destinazione fino al vertice iniziale, quindi inverti l'ordine. Per esempio, se parent[D] = B e parent[B] = A, il percorso scoperto da A a D è A → B → D. Usa un indicatore separato per segnalare che il vertice iniziale non ha padre.

Tuttavia, interpretare «più breve» in senso troppo ampio porta a errori. La BFS garantisce il numero minimo di archi solo quando tutti gli archi possono essere considerati dello stesso costo. Se le strade hanno tempi di percorrenza diversi o i voli hanno tariffe diverse, un percorso che usa due archi può essere più economico o più rapido di uno che ne usa uno solo. In tal caso, la BFS standard non è un algoritmo per il percorso minimo in base al costo. A seconda delle proprietà dei pesi, considera metodi dedicati ai grafi pesati come l'algoritmo di Dijkstra o l'algoritmo di Bellman-Ford. algs4.cs.princeton.edu↗

La BFS è quindi adatta a problemi come «Quanti gradi di separazione ci sono tra due amici?» oppure «Quante mosse servono per raggiungere un punto in una griglia, se spostarsi di una cella in alto, in basso, a sinistra o a destra conta come una mossa?». Al contrario, se l'obiettivo è il tempo minore o il costo più basso, verifica prima che i pesi degli archi siano davvero uguali.

Perché la DFS scende in profondità prima di tornare indietro?

DFS significa Depth-First Search, ovvero ricerca in profondità. Dal vertice corrente, sceglie un vicino non visitato e continua a spostarsi finché non ha esplorato un ramo il più in profondità possibile. Quando raggiunge un vicolo cieco, torna al vertice precedente e cerca un altro vicino che non sia ancora stato esplorato. Questo processo di ritorno è chiamato anche backtracking. ocw.mit.edu↗

La DFS è facile da implementare con chiamate ricorsive. Quando si entra in un vertice, lo si contrassegna anzitutto come visitato, quindi si richiama la stessa funzione di attraversamento per ogni vicino non visitato di quel vertice. Quando una chiamata ricorsiva termina, il controllo torna naturalmente al punto che l'ha chiamata, esprimendo il flusso della discesa in profondità e del successivo backtracking.

La ricorsione non è l'unica possibilità. La DFS può anche essere implementata iterativamente con uno stack esplicito. Uno stack è una struttura dati LIFO (Last In, First Out), cioè l'ultimo elemento inserito è il primo a essere rimosso. Rimuovendo per primo il vertice scoperto più di recente, puoi ottenere un comportamento in profondità. In un'implementazione ricorsiva, lo stack delle chiamate del programma svolge implicitamente questo ruolo. ocw.mit.edu↗gh.cp-algorithms.com↗

I puntatori al padre creati dalla DFS possono anch'essi mostrare un percorso dal vertice iniziale a un vertice. Tuttavia, non è garantito che tale percorso abbia il numero minimo di archi. Poiché la DFS segue il primo ramo scelto il più in profondità possibile, potrebbe scoprire solo in seguito un percorso più breve in un altro ramo. ocw.mit.edu↗

Quali tipi di analisi strutturale usano la DFS?

La DFS mostra il suo valore quando analizza la struttura di un grafo invece di verificare semplicemente la raggiungibilità. L'individuazione delle componenti connesse è un esempio rappresentativo. In un grafo non orientato, eseguire una DFS una volta a partire da un qualunque vertice non visitato trova tutti i vertici connessi a esso come un unico gruppo. Avviare nuovamente la DFS da un altro vertice non visitato trova un altro gruppo.

Il rilevamento dei cicli è un'altra applicazione comune della DFS. Un ciclo è una struttura in cui, seguendo gli archi, si può tornare al punto iniziale o a un vertice già presente nel percorso corrente. In un grafo orientato, puoi rilevare un ciclo distinguendo il caso in cui incontri un vertice che si trova già nel percorso ricorsivo corrente. Ecco perché devi distinguere tra un vertice che è stato semplicemente visitato una volta e uno che si trova attualmente nel percorso di attraversamento.

L'ordinamento topologico dispone dipendenze orientate, come le relazioni di propedeuticità tra attività, in un ordine. È possibile solo in un grafo orientato aciclico, o DAG. Un DAG è un grafo orientato senza cicli che riportino al punto di partenza seguendo le direzioni degli archi. Se esiste un ciclo, sorge una contraddizione: per esempio, B deve terminare prima di A e A deve terminare prima di B; pertanto nessun ordinamento lineare può soddisfare tutti gli archi. Un metodo che utilizza l'ordine di completamento della DFS è una delle basi dell'ordinamento topologico. algs4.cs.princeton.edu↗

Anche l'individuazione delle componenti fortemente connesse è un tema importante basato sulla DFS. Una componente fortemente connessa è un insieme di vertici in un grafo orientato in cui qualunque coppia di vertici appartenenti allo stesso gruppo può raggiungersi reciprocamente. Tuttavia, questo problema non si risolve con una sola semplice DFS; richiede una costruzione algoritmica che usa l'ordine di attraversamento e le direzioni degli archi. algs4.cs.princeton.edu↗

Quali problemi si verificano senza marcatori di visita?

In un grafo generale, un array o un insieme dei vertici visitati non è facoltativo: è essenziale per la terminazione e la correttezza. Per esempio, se A e B sono connessi, puoi andare da A a B e poi tornare da B ad A. Senza controllare lo stato di visita, la DFS può alternare ricorsivamente A e B all'infinito, e la BFS può inserire lo stesso vertice nella coda più volte. ocw.mit.edu↗

Il termine visitato può essere suddiviso in modo leggermente diverso a seconda dell'implementazione. Nella BFS, un vertice viene di solito contrassegnato come «scoperto» nel momento in cui viene aggiunto alla coda. Nella DFS, è comune contrassegnare un vertice come visitato immediatamente quando si entra nella sua funzione. Analisi più sofisticate dei grafi orientati possono distinguere tra uno stato non visitato, uno stato attualmente in esplorazione e uno stato completato.

Il principio di visitare ogni vertice una sola volta è direttamente collegato all'efficienza dell'attraversamento. Se non espandi vertici già elaborati, allora con le liste di adiacenza ispezioni ogni vertice e ogni arco solo un numero limitato di volte. Inoltre, se assegni un puntatore al padre soltanto quando un vertice viene scoperto per la prima volta, è chiaro quale percorso ha scoperto per primo quel vertice.

Per attraversare un intero grafo, è necessario un ciclo esterno. Esamina a turno ogni vertice e, ogni volta che ne trovi uno non ancora visitato, avvia una nuova BFS o DFS da esso. In un grafo non orientato, questo produce un attraversamento per componente connessa. In un grafo orientato, elabora successivamente le aree raggiungibili nelle direzioni degli archi scelte. ocw.mit.edu↗

Perché la complessità temporale dipende dalla rappresentazione del grafo?

La complessità temporale di BFS e DFS viene spesso indicata come $O(\lvert V \rvert + \lvert E \rvert)$. Questa è l'analisi standard quando si usano liste di adiacenza. Una lista di adiacenza memorizza, per ciascun vertice, l'elenco dei vicini direttamente connessi. Con i marcatori di visita, ogni vertice viene elaborato una volta e gli archi sono controllati durante la scansione degli elenchi dei vicini, quindi il lavoro totale è proporzionale al numero di vertici più il numero di archi. ocw.mit.edu↗

Lo spazio aggiuntivo è di solito $O(\lvert V \rvert)$. Comprende l'array dei visitati, l'array dei padri e la coda della BFS o lo stack della DFS. Per la DFS ricorsiva, nello spazio aggiuntivo è incluso anche lo stack delle chiamate richiesto dalla profondità di ricorsione. È utile distinguere tra lo spazio usato per memorizzare il grafo stesso e lo spazio aggiuntivo usato dall'algoritmo di attraversamento. ocw.mit.edu↗

Una matrice di adiacenza memorizza in una tabella l'esistenza di un arco per ogni coppia di vertici. Per trovare i vicini di un vertice, potresti dover ispezionare ogni possibile vertice. Di conseguenza, BFS o DFS che usano una matrice di adiacenza possono tipicamente richiedere $O(\lvert V \rvert^2)$ tempo. Per i grafi sparsi con pochi archi, le liste di adiacenza sono particolarmente efficienti perché analizzano soltanto i vicini effettivamente connessi. ocw.mit.edu↗

La notazione di complessità descrive come l'uso delle risorse tende a crescere all'aumentare della dimensione dell'input. Il tempo di esecuzione effettivo è influenzato anche dagli identificatori dei vertici, dall'implementazione delle liste di adiacenza, dalla disposizione in memoria e dalla dimensione della porzione raggiungibile dal punto iniziale dell'attraversamento. Tuttavia, quando scegli un algoritmo, è sensato verificare anzitutto se il grafo è sparso e come viene rappresentato.

L'ordine effettivo di visita di BFS o DFS è fisso?

No. La BFS segue il principio di elaborare prima i livelli più vicini e la DFS quello di esplorare in profondità il ramo corrente, ma quale vertice venga visitato per primo allo stesso livello o quale ramo venga esplorato per primo tra più vicini dipende dall'ordine di memorizzazione dei vertici adiacenti. gh.cp-algorithms.com↗gh.cp-algorithms.com↗

Per esempio, se l'elenco dei vicini di A è ordinato come B, C, la BFS scopre in genere prima B. Se l'elenco viene modificato in C, B, potrebbe essere scoperto prima C. Questa differenza può avere un effetto maggiore nella DFS. Se cambia il primo vicino scelto, cambia il ramo stesso esplorato in profondità, insieme all'albero di attraversamento e ai percorsi DFS creati mediante i puntatori al padre.

Questo fatto è importante quando si valuta il risultato di un algoritmo. Se un problema richiede «l'ordine di visita lessicograficamente primo», devi ordinare le liste di adiacenza o specificare una regola di priorità. Al contrario, se ti servono soltanto la raggiungibilità, il numero di componenti connesse o le distanze minime in numero di archi, l'ordine dettagliato all'interno dello stesso livello o della stessa profondità potrebbe non essere centrale per il risultato.

In particolare, quando implementi iterativamente la DFS con uno stack, l'ordine in cui i vicini vengono inseriti può essere l'inverso dell'ordine in cui vengono effettivamente rimossi. Se vuoi ottenere lo stesso ordine di visita di un'implementazione ricorsiva che usa un determinato ordine della lista di adiacenza, devi regolare intenzionalmente la direzione con cui i vicini vengono inseriti nello stack. Non si tratta di una definizione diversa di DFS; è una differenza di implementazione causata dal comportamento LIFO.

Quali sono le idee sbagliate e gli errori più comuni?

La prima idea sbagliata è che la BFS risolva ogni tipo di problema di percorso minimo. Come spiegato in precedenza, la BFS garantisce il numero minimo di archi in un grafo non pesato. Se i pesi differiscono, una mossa non ha necessariamente lo stesso valore di un'altra, quindi cambia il modello stesso del problema. algs4.cs.princeton.edu↗algs4.cs.princeton.edu↗

La seconda è presumere che la DFS usi sempre meno memoria della BFS. Includendo gli array dei visitati e lo stato di attraversamento, entrambi gli algoritmi possono in generale usare $O(\lvert V \rvert)$ spazio aggiuntivo. La dimensione massima della coda o dello stack può differire per determinate forme del grafo e implementazioni, ma la sola complessità asintotica non stabilisce un vantaggio incondizionato per nessuno dei due. ocw.mit.edu↗

La terza è credere che la DFS ricorsiva sia sicura per qualunque input. In un grafo con una profondità molto grande, anche la profondità di ricorsione diventa grande. Dovresti tenere conto del limite dello stack delle chiamate del linguaggio e dell'ambiente di esecuzione; in questi casi, un'implementazione iterativa con uno stack esplicito può essere più pratica. È anche importante comprendere che lo stack delle chiamate ricorsive fa parte dello spazio aggiuntivo della DFS. ocw.mit.edu↗

La quarta è trattare un grafo orientato come se fosse non orientato. L'esistenza di un arco da A a B non significa che sia possibile andare da B ad A. Quando memorizzi l'input nelle liste di adiacenza, un grafo non orientato aggiunge di solito un arco alle liste di entrambi i vertici, mentre un grafo orientato lo aggiunge soltanto alla lista del vertice sorgente. Questa differenza modifica il significato di raggiungibilità, connettività e cicli. ocw.mit.edu↗

La quinta è scambiare il risultato di un attraversamento per un unico percorso corretto. Quando più percorsi hanno lo stesso numero minimo di archi, la BFS ne registra uno mediante i puntatori al padre. Anche la DFS può produrre percorsi diversi a seconda dell'ordine dei vicini. Se il percorso stesso richiede una priorità, occorre specificare regole di ordinamento o condizioni aggiuntive nel problema.

Quali criteri usare per scegliere in un problema?

È meglio anzitutto esprimere a parole l'obiettivo. Se la domanda chiede soltanto «È raggiungibile dal punto iniziale?», sono possibili sia BFS sia DFS e puoi scegliere in base all'ambiente di implementazione e all'analisi necessaria in seguito. Se serve il numero minimo di archi, come in «Quante mosse identiche servono per arrivare?», la BFS è la scelta naturale. Se devi seguire un percorso in profondità mentre analizzi la struttura, o se è importante il punto in cui torni indietro, probabilmente è appropriata la DFS.

Successivamente, verifica che cosa rappresentano gli archi. Determina se ogni spostamento ha lo stesso costo oppure se sono coinvolti pesi come tempo, distanza o costo. Se esistono pesi, non applicare direttamente la proprietà di percorso minimo della BFS. Controlla inoltre in anticipo se il grafo è orientato, se sono possibili cicli e se devi esaminare l'intero grafo. ocw.mit.edu↗algs4.cs.princeton.edu↗

I criteri di selezione possono essere riassunti come segue.

Infine, considera la dimensione e la rappresentazione dell'input. Per un grafo sparso, le liste di adiacenza e l'analisi standard $O(\lvert V \rvert + \lvert E \rvert)$ per BFS e DFS sono una buona scelta. In ambienti in cui la profondità di ricorsione può essere un problema, considera una DFS iterativa. Se l'ordine di visita influenza la valutazione o le regole aziendali, anche l'ordinamento delle liste di adiacenza fa parte della progettazione.

Conclusione: gli obiettivi e le condizioni dell'attraversamento contano più dei nomi

BFS e DFS sono strategie diverse per attraversare a fondo un grafo. La BFS usa una coda per espandersi a partire dai vertici vicini e ha il vantaggio di fornire percorsi con il numero minimo di archi nei grafi non pesati. La DFS usa la ricorsione o uno stack per esplorare in profondità un ramo e tornare indietro, costituendo la base di molti metodi che lavorano con la struttura dei grafi, comprese le componenti connesse, i cicli e l'ordinamento topologico nei DAG. ocw.mit.edu↗algs4.cs.princeton.edu↗

Entrambe richiedono marcatori di visita e in genere hanno la stessa complessità temporale asintotica quando usano liste di adiacenza. Pertanto, la chiave per scegliere tra loro non è una singola etichetta come la velocità, ma ciò che definisce un percorso più breve, se gli archi sono pesati, come debbano essere interpretate direzione e cicli e se l'intero grafo debba essere elaborato. Distinguere prima queste condizioni consente di usare BFS e DFS per lo scopo corretto.