La differenza principale tra BFS e DFS è che BFS procede livello per livello mentre DFS segue prima un percorso dall’inizio al nodo finale (vertice), poi un altro percorso dall’inizio alla fine, e così via fino a quando tutti i nodi vengono visitati. Inoltre, BFS utilizza la coda per memorizzare i nodi mentre DFS utilizza lo stack per l’attraversamento dei nodi.
BFS e DFS sono i metodi di attraversamento utilizzati nella ricerca di un grafico. L’attraversamento del grafico è il processo di visita di tutti i nodi del grafico. Un grafico è un gruppo di vertici ‘V ‘e Bordi’ E’ che si collegano ai vertici.
Contenuto: BFS Vs DFS
- Comparison Chart
- Definition
- Key Differences
- Conclusion
Comparison Chart
| Basis for comparison | BFS | DFS |
|---|---|---|
| Basic | Vertex-based algorithm | Edge-based algorithm |
| Data structure used to store the nodes | Queue | Stack |
| Memory consumption | Inefficient | Efficient |
| Structure dell’albero costruito | Largo e corto | Stretto e lungo |
| Attraversando la moda | I vertici più antichi non visitati vengono esplorati all’inizio. | I vertici lungo il bordo sono esplorati all’inizio. |
| Ottimalità | Ottimale per trovare la distanza più breve, non in costo. | Non ottimale |
| Applicazione | Esamina grafo bipartito, componente collegato e percorso più breve presente in un grafico. | Esamina il grafico connesso a due bordi, il grafico fortemente connesso, il grafico aciclico e l’ordine topologico. |
Definizione di BFS
Larghezza Prima ricerca (BFS) è il metodo di attraversamento utilizzato nei grafici. Utilizza una coda per memorizzare i vertici visitati. In questo metodo l’enfasi è sui vertici del grafico, un vertice viene selezionato in un primo momento, quindi viene visitato e contrassegnato. I vertici adiacenti al vertice visitato vengono quindi visitati e memorizzati nella coda in sequenza.
Allo stesso modo, i vertici memorizzati vengono quindi trattati uno per uno e vengono visitati i loro vertici adiacenti. Un nodo è completamente esplorato prima di visitare qualsiasi altro nodo nel grafico, in altre parole, attraversa prima i nodi inesplorati più superficiali.
Esempio
Abbiamo un grafico i cui vertici sono A, B, C, D, E, F, G. Considerando A come punto di partenza. I passaggi coinvolti nel processo sono:
- Il vertice A viene espanso e memorizzato nella coda.
- Vertici B, D e G successori di A, vengono espansi e memorizzati nella coda nel frattempo Vertice A rimosso.
- Ora B all’estremità anteriore della coda viene rimosso insieme alla memorizzazione dei suoi vertici successori E e F.
- Vertex D è al front-end della coda viene rimosso, e il suo nodo collegato F è già visitato.
- Vertex G viene rimosso dalla coda e ha il successore E che è già stato visitato.
- Ora E e F vengono rimossi dalla coda e il suo vertice successore C viene attraversato e memorizzato nella coda.
- Alla fine anche C viene rimosso e la coda è vuota, il che significa che abbiamo finito.
- L’uscita generata è-A, B, D, G, E, F, C.
Applicazioni
BFS può essere utile per trovare se il grafico ha componenti collegati o meno. E inoltre può essere utilizzato per rilevare un grafico bipartito.
Un grafo è bipartito quando i vertici del grafo sono divisi in due insiemi disgiunti; non esistono due vertici adiacenti nello stesso insieme. Un altro metodo di controllo di un grafico bipartito è quello di controllare il verificarsi di un ciclo dispari nel grafico. Un grafo bipartito non deve contenere ciclo dispari.
BFS è anche meglio a trovare il percorso più breve nel grafico potrebbe essere visto come una rete.
Definizione di DFS
Depth First Search (DFS) metodo di attraversamento utilizza lo stack per memorizzare i vertici visitati. DFS è il metodo basato sul bordo e funziona in modo ricorsivo in cui i vertici vengono esplorati lungo un percorso (bordo). L’esplorazione di un nodo viene sospesa non appena viene trovato un altro nodo inesplorato e i nodi inesplorati più profondi vengono attraversati in primo luogo. DFS attraversa / visita ogni vertice esattamente una volta e ogni bordo viene ispezionato esattamente due volte.
Esempio
Simile a BFS consente di prendere lo stesso grafico per l’esecuzione di operazioni DFS e i passaggi coinvolti sono:
- Considerando A come vertice iniziale che viene esplorato e memorizzato nello stack.
- B successore vertice di A è memorizzato nello stack.
- Il vertice B ha due successori E e F, tra cui alfabeticamente E viene esplorato per primo e memorizzato nello stack.
- Il successore di vertex E, cioè G è memorizzato nello stack.
- Il vertice G ha due vertici collegati, ed entrambi sono già visitati, quindi G viene estratto dallo stack.
- Allo stesso modo, E s anche rimosso.
- Ora, il vertice B è in cima allo stack, il suo altro nodo(vertice) F è esplorato e memorizzato nello stack.
- Vertex F ha due successori C e D, tra loro C viene attraversato per primo e memorizzato nello stack.
- Vertex C ha solo un predecessore già visitato, quindi viene rimosso dallo stack.
- Ora il vertice D collegato a F viene visitato e memorizzato nello stack.
- Poiché il vertice D non ha nodi non visitati, quindi D viene rimosso.
- Allo stesso modo, vengono spuntati anche F, B e A.
- L’uscita generata è-A, B, E, G, F, C, D.
Applicazione
Le applicazioni di DFS comprende l’ispezione di due bordo collegato grafico, fortemente collegato grafico, aciclico grafico, e ordine topologico.
Un grafico è chiamato due bordi collegati se e solo se rimane connesso anche se uno dei suoi bordi viene rimosso. Questa applicazione è molto utile, nelle reti di computer in cui il fallimento di un collegamento nella rete non influenzerà la rete rimanente, e sarebbe ancora connesso.
Il grafico fortemente connesso è un grafico in cui deve esistere un percorso tra una coppia ordinata di vertici. DFS viene utilizzato nel grafico diretto per cercare il percorso tra ogni coppia ordinata di vertici. DFS può facilmente risolvere i problemi di connettività.
Differenze chiave tra BFS e DFS
- BFS è un algoritmo basato su vertici mentre DFS è un algoritmo basato su bordi.
- La struttura dei dati della coda viene utilizzata in BFS. D’altra parte, DFS utilizza stack o ricorsione.
- Lo spazio di memoria viene utilizzato in modo efficiente in DFS mentre l’utilizzo dello spazio in BFS non è efficace.
- BFS è algoritmo ottimale mentre DFS non è ottimale.
- DFS costruisce alberi stretti e lunghi. Come contro, BFS costruisce albero largo e corto.
Conclusione
BFS e DFS, entrambe le tecniche di ricerca del grafico hanno un tempo di esecuzione simile ma un consumo di spazio diverso, DFS prende spazio lineare perché dobbiamo ricordare un singolo percorso con nodi inesplorati, mentre BFS mantiene ogni nodo in memoria.
DFS produce soluzioni più profonde e non è ottimale, ma funziona bene quando la soluzione è densa mentre BFS è ottimale che cerca inizialmente l’obiettivo ottimale.