Differenza tra BFS e DFS

BFS vs DFS

Larghezza Prima ricerca (noto anche come BFS) è un metodo di ricerca utilizzato per ampliare tutti i nodi di un particolare grafico. Compie questo compito cercando ogni singola soluzione per esaminare ed espandere questi nodi (o una combinazione di sequenze in esso). Pertanto, un BFS non utilizza un algoritmo euristico (o un algoritmo che cerca una soluzione attraverso più scenari). Dopo che tutti i nodi sono stati ottenuti, vengono aggiunti a una coda nota come coda First In, First Out. Quei nodi che non sono stati esplorati sono "memorizzati" in un contenitore contrassegnato come "aperto"; una volta esplorati vengono trasportati in un contenitore contrassegnato come "chiuso".

Depth First Search (noto anche come DFS) è un metodo di ricerca che si scava più a fondo in un nodo figlio di una ricerca fino a quando non viene raggiunto un obiettivo (o finché non vi è un nodo senza altre permutazioni o "figli"). Dopo aver trovato un obiettivo, la ricerca torna a un nodo precedente che è andato con una soluzione, ripetendo il processo fino a quando tutti i nodi sono stati cercati con successo. Di conseguenza, i nodi continuano a essere messi da parte per ulteriori esplorazioni - questa è chiamata implementazione non ricorsiva.

Le caratteristiche del BFS sono la complessità dello spazio e del tempo, la completezza, la prova di completezza e l'ottimalità. La complessità dello spazio si riferisce alla proporzione del numero di nodi al livello più profondo di una ricerca. La complessità temporale si riferisce alla quantità effettiva di "tempo" utilizzata per considerare ogni percorso che un nodo intraprenderà in una ricerca. La completezza è essenzialmente una ricerca che trova una soluzione in un grafico indipendentemente dal tipo di grafico. La prova della completezza è il livello più superficiale in cui si trova un obiettivo in un nodo ad una profondità definita. Infine, l'ottimalità si riferisce a un BFS che non è ponderato, ovvero un grafico utilizzato per il costo unitario.

Un DFS è l'output più naturale che utilizza un albero spanning - che è un albero composto da tutti i vertici e alcuni bordi in un grafo non orientato. In questa formazione, il grafico è diviso in tre classi: Bordi avanzati, che puntano da un nodo a un nodo figlio; bordi posteriori, che puntano da un nodo a un nodo precedente; e bordi trasversali, che non fanno nessuno di questi.

Sommario:

1. Un BFS cerca ogni singola soluzione in un grafico per espandere i suoi nodi; un DFS scava in profondità all'interno di un nodo figlio fino a quando non viene raggiunto un obiettivo.

2. Le caratteristiche di un BFS sono la complessità dello spazio e del tempo, la completezza, la prova di completezza e l'ottimalità; l'output più naturale per un DFS è uno spanning tree con tre classi: bordi anteriori, bordi posteriori e bordi incrociati.