Cos'è BFS?
BFS è un algoritmo utilizzato per rappresentare graficamente i dati o per cercare alberi o strutture di attraversamento. 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 quindi 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 fino a quando 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 sull'albero binario DFS, imparerai:
- Cos'è BFS?
- 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à. L'esecuzione dell'algoritmo 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 appare un vicolo cieco in qualsiasi iterazione. La forma completa di DFS è la ricerca in profondità.
Esempio di BFS
Nel seguente esempio di DFS, abbiamo usato il grafo con 6 vertici.
Esempio di BFS
Passo 1)
Hai un grafico di sette numeri che vanno da 0 a 6.
Passo 2)
0 o zero è stato contrassegnato come nodo radice.
Passaggio 3)
0 viene visitato, contrassegnato e inserito nella struttura dati della coda.
Passaggio 4)
I rimanenti 0 nodi adiacenti e non visitati vengono visitati, contrassegnati e inseriti nella coda.
Passaggio 5)
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.
Passo 1)
Siamo partiti dal vertice 0. L'algoritmo inizia inserendolo nella lista visitata e contemporaneamente inserendo tutti i suoi vertici adiacenti nella struttura dati chiamata stack.
Passo 2)
Visiterai l'elemento, che si trova in cima alla pila, ad esempio 1 e andrai 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 nella pila e lo visitiamo.
Passaggio 4)
Infine, visiteremo l'ultimo vertice 3, non ha nodi adiacenti non visitati. Abbiamo completato l'attraversamento del grafico utilizzando l'algoritmo 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 del prossimo luogo da visitare. | Utilizza una pila per tenere traccia del prossimo luogo da visitare. |
| BFS attraversa in base al livello dell'albero. | DFS attraversa 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 eseguire il backtracking in BFS. | È necessario eseguire il backtracking in DFS. |
| Non puoi mai essere intrappolato in cicli finiti. | Puoi essere intrappolato in loop infiniti. |
| Se non trovi alcun obiettivo, potrebbe essere necessario espandere molti nodi prima che venga trovata la soluzione. | Se non trovi alcun obiettivo, potrebbe verificarsi il backtracking del nodo foglia. |
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 più breve tempo possibile con elevata 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.
Crawler web:
I motori di ricerca o i web crawler possono creare facilmente più livelli di indici utilizzando BFS. L'implementazione di BFS inizia dalla fonte, che è 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 di DFS
Ecco le applicazioni importanti 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.
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.
Ricerca del percorso:
Possiamo specializzarci nell'algoritmo DFS per cercare un percorso tra due vertici.
Ordinamento topologico:
Viene utilizzato principalmente per la pianificazione dei 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 dell'ordine delle attività di compilazione.
Ricerca di componenti fortemente connessi di un grafico:
Viene utilizzato nel grafico DFS quando è presente un percorso da ogni vertice nel grafico ad altri vertici rimanenti.
Risolvere i puzzle con una sola soluzione:
L'algoritmo DFS può essere facilmente adattato per cercare tutte le soluzioni in un labirinto includendo nodi sul percorso esistente nel set visitato.
DIFFERENZE PRINCIPALI:
- BFS trova il percorso più breve per la destinazione, mentre DFS va alla fine di una sottostruttura, quindi esegue il backtrack.
- La forma completa di BFS è Breadth-First Search mentre la forma completa di DFS è Depth First Search.
- BFS utilizza una coda per tenere traccia della posizione successiva da visitare. mentre DFS utilizza uno stack per tenere traccia della posizione successiva da visitare.
- BFS attraversa in base al livello della struttura mentre DFS attraversa in base alla profondità della struttura.
- BFS viene implementato utilizzando l'elenco FIFO, mentre DFS viene implementato utilizzando l'elenco LIFO.
- In BFS, non puoi mai essere intrappolato in loop finiti mentre in DFS puoi essere intrappolato in loop infiniti.