Differenza tra BFS VS DFS

Breadth-First Search (BFS) e Depth First Search (DFS) sono due importanti algoritmi utilizzati per la ricerca. Breadth-First Search avvia la ricerca dal primo nodo, quindi passa attraverso i livelli più vicini al nodo principale mentre l'algoritmo Depth First Search inizia con il primo nodo e quindi completa il percorso verso il nodo finale del rispettivo percorso. Entrambi gli algoritmi attraversano ogni nodo durante la ricerca. Vengono scritti codici diversi per i due algoritmi per eseguire il processo di attraversamento. Sono anche considerati importanti algoritmi di ricerca nell'intelligenza artificiale.

In questo argomento, impareremo a conoscere BFS VS DFS.

Come funzionano BFS e DFS?

Il meccanismo di funzionamento di entrambi gli algoritmi è spiegato di seguito con esempi. Fare riferimento a loro per una migliore comprensione dell'approccio utilizzato.

Esempio di ricerca breadth-first

  • Passaggio 1: N1 è il nodo principale, quindi inizierà da qui. N1 è collegato con tre nodi N2, N3 e N4. Tutti e tre i nodi non sono ancora visitati. Quindi, partiamo da N2 e lo memorizziamo nella coda. Pertanto, la coda denominata Q contiene solo N2.

Q: N2

  • Passaggio 2: Successivamente il nodo collegato a N1 è N3. Poiché abbiamo attraversato o visitato il nodo, lo memorizzeremo nella coda. Quindi, la coda aggiornata è

Q: N3, N2

  • Passaggio 3: Successivamente il nodo collegato al nodo principale è N4. Lo memorizzeremo nella coda.

Q: N4, N3, N2

  • Passaggio 4: tutti i nodi collegati a N1 sono archiviati nella coda. Ora, rimuoviamo N2 dalla coda secondo il principio First in First Out (FIFO) e troviamo i nodi che sono collegati a N2, cioè N5. N5 non viene visitato una volta, quindi lo memorizzeremo nella coda.

Q: N5, N4, N3

  • Passaggio 5: vengono visitati tutti i vertici, quindi continuiamo a rimuovere i nodi dalla coda fino a quando non è vuoto.

Profondità Primo esempio di ricerca

  • Passaggio 1: inizieremo con N1 come nodo iniziale e lo memorizzeremo in uno stack S. N1 è collegato con tre nodi vicini N2, N3 e N4. A partire da N2 (puoi iniziare in ordine alfabetico o numerico), lo metteremo nello stack.

S: N2 (in alto), N1

  • Step 2: Ora, i nodi vicini di N2 sono N1 e N5. Poiché N1 è già presente nello stack significa che è visitato, quindi prenderemo N5 e lo metteremo nello stack S.

S: N5 (in alto), N2, N1

  • Passaggio 3: ora, i nodi vicini di N5 sono N3 e N4. Iniziamo N3 e lo mettiamo in pila.

S: N3 (in alto), N5, N2, N1

Ora N3 è collegato a N5 e N1 che sono già presenti nello stack, il che significa che sono visitati, quindi rimuoveremo N3 dallo stack secondo il principio del principio Last in First Out (LIFO).

S: N5 (in alto), N2, N1

  • Step 4: Ora inseriremo l'ultimo nodo che non ci siamo imbattuti nell'intero attraversamento in N4 e lo metteremo nello stack.

S: N4 (in alto), N5, N2, N1

  • Passo 5: Ora non siamo esclusi da nessun altro nodo, quindi controlleremo nello stack se ci sono nodi collegati ai rispettivi nodi presenti in esso che non sono visitati. Se vengono visitati tutti i nodi collegati, rimuoveremo i nodi presenti nello stack. Ad esempio, N4 non ha nodi di connessione che non abbiamo verificato, quindi lo rimuoveremo dallo stack. Allo stesso modo, possiamo verificare la presenza di altri nodi. L'algoritmo si interrompe quando lo stack è vuoto.

Confronto testa a testa tra BFS VS DFS (infografica)

Di seguito sono riportate le prime 6 differenze tra BFS VS DFS

Differenze chiave tra BFS e DFS

Discutiamo alcune delle principali differenze chiave tra BFS e DFS

  • Breadth-First Search (BFS) inizia dal nodo radice e visita tutti i rispettivi nodi ad esso collegati mentre DFS parte dal nodo radice e completa il percorso completo collegato al nodo.
  • BFS segue l'approccio di Queue mentre DFS segue l'approccio di Stack.
  • L'approccio utilizzato in BFS è ottimale mentre il processo utilizzato in DFS non è ottimale.
  • Se il nostro obiettivo è trovare il percorso più breve di BFS è preferito a DFS.

Tabella di confronto BFS e DFS

Discutiamo il miglior confronto tra BFS e DFS

BFSDFS
La forma completa di BFS è Breadth-First Search.La forma completa di DFS è Depth First Search
BFS ha lo scopo di trovare la distanza più breve e inizia dal primo nodo o radice e si sposta su tutti i suoi nodi collegati ai rispettivi nodi. È possibile ottenere una visione chiara del suo meccanismo di funzionamento dopo aver esaminato l'esempio seguente.DFS segue un approccio basato sulla profondità e completa il percorso completo attraverso tutti i nodi collegati al rispettivo nodo. È possibile ottenere una visione chiara del suo meccanismo di funzionamento dopo aver esaminato l'esempio seguente.
Viene fatto usando il principio Queue, che è l'approccio First In First Out (FIFO).Viene fatto usando il principio Stack, che è l'approccio Last In First out (LIFO).
I nodi che vengono attraversati più di una volta vengono rimossi dalla coda.I nodi visitati vengono inseriti nello stack e successivamente, se non ci sono più nodi da visitare, vengono rimossi.
È relativamente più lento della prima ricerca di profondità.È più veloce dell'algoritmo Breadth-First Search.
L'allocazione di memoria è più dell'algoritmo Depth First Search.L'allocazione di memoria è relativamente inferiore all'algoritmo di ricerca breadth-first

Conclusione

Esistono molte applicazioni in cui gli algoritmi di cui sopra vengono utilizzati come machine learning o per trovare soluzioni correlate all'intelligenza artificiale ecc. Vengono principalmente utilizzati nei grafici per scoprire se è bipartito o meno, per rilevare cicli o componenti collegati. Sono anche considerati algoritmi importanti per trovare il percorso o trovare la distanza più breve. A seconda delle esigenze dell'azienda, possiamo usare due algoritmi. Tuttavia, Breadth-First Search è considerato un modo ottimale piuttosto che l'algoritmo Depth First Search.

Articoli consigliati

Questa è una guida a BFS VS DFS. Qui discutiamo le differenze chiave tra BFS e DFS con infografica e tabella comparativa. Puoi anche dare un'occhiata ai seguenti articoli per saperne di più -

  1. Algoritmo BFS
  2. TeraData vs Oracle
  3. Big Data vs Data Warehouse
  4. Big Data vs Apache Hadoop: I 4 migliori confronti che devi imparare

Categoria: