BFS vs DFS – Differenza tra loro

Differenza chiave tra BFS e DFS

  • BFS trova il percorso più breve verso la destinazione, mentre DFS va alla fine di un sottoalbero, quindi torna indietro.
  • La forma completa di BFS è Ricerca in ampiezza, mentre la forma completa di DFS è Ricerca in profondità.
  • BFS utilizza una coda per tenere traccia della prossima posizione da visitare. mentre DFS utilizza uno stack per tenere traccia della successiva posizione da visitare.
  • BFS si sposta in base al livello dell'albero, mentre DFS si sposta in base alla profondità dell'albero.
  • BFS è implementato utilizzando un elenco FIFO; d'altro canto, DFS viene implementato utilizzando un elenco LIFO.
  • In BFS, non puoi mai rimanere intrappolato in cicli finiti, mentre in DFS puoi essere intrappolato in cicli infiniti.
Differenza tra BFS e DFS
Differenza tra BFS e DFS

Cos'è BFS?

BFS è un algoritmo utilizzato per rappresentare graficamente dati o cercare alberi o attraversare strutture. L'algoritmo visita e contrassegna in modo efficiente tutti i nodi chiave in un grafico in modo accurato in larghezza.

Questo algoritmo seleziona un singolo nodo (punto iniziale o sorgente) in un grafico e poi visita tutti i nodi adiacenti al nodo selezionato. Una volta che l'algoritmo visita e contrassegna il nodo di partenza, si sposta verso i nodi non visitati più vicini e li analizza.

Una volta visitati, tutti i nodi vengono contrassegnati. Queste iterazioni continuano finché tutti i nodi del grafico non sono stati visitati e contrassegnati con successo. La forma completa di BFS è la ricerca in ampiezza.

Cos'è DFS?

DFS è un algoritmo per trovare o attraversare grafici o alberi in direzione della profondità. L'esecuzione dell'algoritmo inizia dal nodo radice ed esplora ogni ramo prima di tornare indietro. Utilizza una struttura dati stack per ricordare, ottenere il vertice successivo e avviare una ricerca, ogni volta che appare un vicolo cieco in qualsiasi iterazione. La forma completa di DFS è la ricerca in profondità.

Differenza tra albero binario BFS e DFS

Ecco le differenze importanti tra BFS e DFS.

BFS DFS
BFS trova il percorso più breve per raggiungere la destinazione. DFS va alla fine di un sottoalbero, quindi torna indietro.
La forma completa di BFS è la ricerca in ampiezza. La forma completa di DFS è Depth First Search.
Utilizza una coda per tenere traccia della prossima posizione da visitare. Utilizza uno stack per tenere traccia della prossima posizione da visitare.
BFS si sposta in base al livello dell'albero. DFS si sposta in base alla profondità dell'albero.
È implementato utilizzando l'elenco FIFO. È implementato utilizzando l'elenco LIFO.
Richiede più memoria rispetto a DFS. Richiede meno memoria rispetto a BFS.
Questo algoritmo fornisce la soluzione del percorso più superficiale. Questo algoritmo non garantisce la soluzione del percorso più superficiale.
Non è necessario tornare indietro in BFS. È necessario fare marcia indietro in DFS.
Non puoi mai rimanere intrappolato in cicli finiti. Puoi rimanere intrappolato in cicli infiniti.
Se non trovi alcun obiettivo, potrebbe essere necessario espandere molti nodi prima di trovare la soluzione. Se non trovi alcun obiettivo, potrebbe verificarsi il backtracking del nodo foglia.

Esempio di BFS

Nel seguente esempio di BFS, abbiamo utilizzato un grafico con 6 vertici.

Esempio di BFS

Passo 1)

Esempio di BFS

Hai un grafico di sette numeri che vanno da 0 a 6.

Passo 2)

Esempio di BFS

0 o zero è stato contrassegnato come nodo radice.

Passo 3)

Esempio di BFS

0 viene visitato, contrassegnato e inserito nella struttura dati della coda.

Passo 4)

Esempio di BFS

I restanti 0 nodi adiacenti e non visitati vengono visitati, contrassegnati e inseriti nella coda.

Passo 5)

Esempio di BFS

Le iterazioni di attraversamento vengono ripetute finché non vengono visitati tutti i nodi.

Esempio di DFS

Nel seguente esempio di DFS abbiamo utilizzato un grafo non orientato con 5 vertici.

Esempio di DFS

Passo 1)

Esempio di DFS

Siamo partiti dal vertice 0. L'algoritmo inizia inserendolo nell'elenco visitato e inserendo simultaneamente tutti i suoi vertici adiacenti nell'elenco struttura dati chiamato pila.

Passo 2)

Esempio di DFS

Visiterai l'elemento che si trova in cima allo stack, ad esempio 1, e andrai ai nodi adiacenti. È perché 0 è già stato visitato. Visitiamo quindi il vertice 2.

Passo 3)

Esempio di DFS

Il vertice 2 ha un vertice vicino non visitato in 4. Pertanto, lo aggiungiamo allo stack e lo visitiamo.

Passo 4)

Esempio di DFS

Infine visiteremo l'ultimo vertice 3, non ha nodi adiacenti non visitati. Abbiamo completato l'attraversamento del grafico utilizzando l'algoritmo DFS.

Esempio di DFS

Applicazioni di BFS

Ecco le applicazioni di BFS:

Grafici non ponderati

L'algoritmo BFS può facilmente creare il percorso più breve e uno spanning tree minimo per visitare tutti i vertici del grafico nel minor tempo possibile con elevata precisione.

Reti P2P

BFS può essere implementato per localizzare tutti i nodi più vicini o adiacenti in una rete peer to peer. Ciò troverà i dati richiesti più velocemente.

Web Crawler

Motori di ricerca oppure i web crawler possono facilmente creare più livelli di indici utilizzando BFS. L'implementazione di BFS inizia dalla fonte, ovvero la pagina Web, e quindi visita tutti i collegamenti da quella fonte.

Trasmissione in rete

Un pacchetto trasmesso è guidato dall'algoritmo BFS per trovare e raggiungere tutti i nodi di cui ha l'indirizzo.

Applicazioni del DFS

Ecco alcune importanti applicazioni di DFS:

Grafico ponderato

In un grafico ponderato, l'attraversamento del grafico DFS genera l'albero del percorso più breve e l'albero di copertura minimo.

Rilevazione di un ciclo in un grafico

Un grafico ha un ciclo se troviamo un bordo posteriore durante DFS. Pertanto, dovremmo eseguire DFS per il grafico e verificare i bordi posteriori.

Trovare il percorso

Possiamo specializzarci nell'algoritmo DFS per cercare un percorso tra due vertici.

Ordinamento topologico

Viene utilizzato principalmente per pianificare i lavori dalle dipendenze indicate nel gruppo di lavori. Nell'informatica, viene utilizzato nella pianificazione delle istruzioni, nella serializzazione dei dati, nella sintesi logica e nella determinazione dell'ordine delle attività di compilazione.

Ricerca di componenti fortemente connesse di un grafico

Viene utilizzato nel grafico DFS quando è presente un percorso da ogni vertice del grafico agli altri vertici rimanenti.

Risolvere enigmi con una sola soluzione

L'algoritmo DFS può essere facilmente adattato per cercare tutte le soluzioni in un labirinto includendo i nodi sul percorso esistente nell'insieme visitato.