BFS vs DFS: Conosci la differenza

Che cosè BFS ?

BFS è un algoritmo utilizzato per rappresentare graficamente i dati o per cercare alberi o strutture di attraversamento. Lalgoritmo 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 grafo e quindi visita tutti i nodi adiacenti al nodo selezionato. Una volta che lalgoritmo 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 Breadth-first.

In questo BSF vs. Esercitazione sullalbero binario di DFS, imparerai:

• Cosè BFS?
• Che cosè DFS?
• Esempio di BFS
• Esempio di DFS
• Differenza tra BFS e albero binario DFS
• Applicazioni di BFS
• Applicazioni di DFS

Cosè DFS?

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

Esempio di BFS

Nel seguente esempio di DFS, abbiamo ho usato un grafo con 6 vertici.

Esempio di BFS

Passaggio 1)

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

Passaggio 2)

0 o zero è stato contrassegnato come nodo radice.

Passaggio 3)

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

Passaggio 4)

Restanti 0 adiacenti e non visitati i nodi vengono visitati, contrassegnati e inseriti nella coda.

Passaggio 5)

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

Esempio di DFS

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

Passaggio 1)

Siamo partiti dal vertice 0. Lalgoritmo inizia inserendolo nella lista visitata e contemporaneamente inserendo tutti i suoi vertici adiacenti nei dati struttura chiamata stack.

Passaggio 2)

Visiterai lelemento , che si trova in cima alla pila, ad esempio 1 e va ai suoi nodi adiacenti. È perché 0 è già stato visitato. Pertanto, visitiamo il vertice 2.

Passaggio 3)

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

Passaggio 4)

Infine, visiteremo lultimo vertice 3, non ha nodi adiacenti non visitati. Abbiamo completato lattraversamento del grafico utilizzando lalgoritmo DFS.

Differenza tra BFS e albero binario DFS

BFS	DFS
BFS trova il percorso più breve per la destinazione.	DFS va in fondo a una sottostruttura, quindi torna indietro .
La forma completa di BFS è Breadth-First Search.	La forma completa di DFS è Depth First Search.
Utilizza una coda per tenere traccia della posizione successiva da visitare.	Utilizza una pila per tenere traccia della posizione successiva da visitare.
BFS attraversa in base al livello dellalbero.	DFS attraversa in base alla profondità dellalbero.
È implementato utilizzando FI Elenco FO.	È implementato utilizzando LIFO list.
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 il backtracking in BFS.	Cè una necessità di backtracking in DFS.
Non puoi mai essere intrappolato in loop finiti.	Puoi essere intrappolato in loop infiniti.
Se non trovi alcun obiettivo, potresti dover espandere molti nodi prima che la soluzione venga trovata.	Se non trovi alcun obiettivo, il backtracking del nodo foglia potrebbe si verificano.

Applicazioni di BFS

Ecco le applicazioni di BFS:

Non pesate Grafici:

Lalgoritmo 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 alta precisione.

Reti P2P:

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

Web crawler:

i motori di ricerca o i web crawler possono facilmente creare più livelli di indici utilizzando BFS. Limplementazione di BFS inizia dalla fonte, che è la pagina web, e poi visita tutti i collegamenti da quella fonte.

Network Broadcasting:

Un pacchetto trasmesso è guidato dallalgoritmo BFS per trovare e raggiungere tutti i nodi per i quali ha lindirizzo.

Applicazioni di DFS

Ecco importanti applicazioni di DFS:

Grafico pesato:

In un grafico ponderato, lattraversamento del grafico DFS genera lalbero del percorso più breve e lalbero di copertura minimo.

Rilevamento di un ciclo in un grafico:

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

Path Finding:

Possiamo specializzarci nellalgoritmo DFS per cercare un percorso tra due vertici.

Ordinamento topologico:

Viene utilizzato principalmente per programmare i lavori dalle dipendenze date tra il gruppo di lavori. In informatica, viene utilizzato nella pianificazione delle istruzioni, nella serializzazione dei dati, nella sintesi logica, nella determinazione dellordine delle attività di compilazione.

Ricerca di componenti fortemente connessi di un grafico:

Viene utilizzato nel grafico DFS quando cè un percorso da ogni vertice nel grafico ad altri vertici rimanenti.

Risolvere enigmi con una sola soluzione:

Lalgoritmo DFS può essere facilmente adattato per cercare tutte le soluzioni in un labirinto includendo nodi sul percorso esistente nel set visitato.