BFS e DFS sono i metodi di attraversamento utilizzati nella ricerca di un grafico. Il traversal grafico è il processo di visita di tutti i nodi del grafico. Un grafico è un gruppo di V di Vertices e 'E' di Edges che si connettono ai vertici.
Grafico comparativo
| Base per il confronto | BFS | DFS |
|---|---|---|
| Di base | Algoritmo basato su vertici | Algoritmo basato sul bordo |
| Struttura dei dati utilizzata per memorizzare i nodi | Coda | Pila |
| Consumo di memoria | Inefficiente | Efficiente |
| Struttura dell'albero costruito | Largo e corto | Stretto e lungo |
| Attraversando la moda | Inizialmente vengono esplorati i vertici non visitati più vecchi. | I vertici lungo il bordo sono esplorati all'inizio. |
| ottimalità | Ottimale per trovare la distanza più breve, non nel costo. | Non ottimale |
| Applicazione | Esamina il grafico bipartito, il componente connesso e il percorso più breve presenti in un grafico. | Esamina il grafico connesso a due lati, 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. Usa una coda per memorizzare i vertici visitati. In questo metodo l'enfasi è sui vertici del grafico, un vertice viene selezionato inizialmente, 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 i loro vertici adiacenti vengono visitati. 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.
- I successori B, D e G successori di A, vengono espansi e archiviati nella coda nel frattempo Vertex A rimosso.
- Ora B nella parte anteriore della coda viene rimosso insieme a memorizzare i suoi successori vertici E e F.
- Il vertice D è all'estremità anteriore della coda è rimosso e il suo nodo connesso F è già visitato.
- Il vertice G viene rimosso dalla coda e ha il successore E già visitato.
- Ora E e F vengono rimossi dalla coda e il suo vertice successore C viene attraversato e memorizzato nella coda.
- Finalmente anche C viene rimosso e la coda è vuota, il che significa che abbiamo finito.
- L'output generato è - A, B, D, G, E, F, C.
BFS può essere utile per scoprire se il grafico ha o meno componenti collegati . E può anche essere usato per rilevare un grafico bipartito .
Un grafico è bipartito quando i vertici del grafico sono divisi in due gruppi disgiunti; non ci sono due vertici adiacenti nello stesso set. Un altro metodo per controllare un grafico bipartito è controllare l'occorrenza di un ciclo dispari nel grafico. Un grafico bipartito non deve contenere un ciclo dispari.
BFS è anche meglio nel trovare il percorso più breve nel grafico potrebbe essere visto come una rete.
Definizione di DFS
Il metodo di attraversamento della profondità First Search (DFS) utilizza lo stack per la memorizzazione dei vertici visitati. DFS è il metodo basato sul bordo e funziona in modo ricorsivo dove i vertici sono esplorati lungo un percorso (bordo). L'esplorazione di un nodo viene sospesa non appena viene trovato un altro nodo inesplorato e i nodi più inesplorati più profondi vengono attraversati al primo posto. DFS attraversa / visita ogni vertice esattamente una volta e ogni spigolo viene ispezionato esattamente due volte.
Esempio
Simile a BFS consente di prendere lo stesso grafico per eseguire operazioni DFS e i passaggi coinvolti sono:
- Considerando A come il vertice iniziale che viene esplorato e archiviato nello stack.
- B Il vertice successore di A è memorizzato nello stack.
- Il vertice B ha due successori E ed F, tra questi alfabeticamente E viene esplorato per primo e archiviato nello stack.
- Il successore del vertice E, cioè G è memorizzato nello stack.
- Il vertice G ha due vertici collegati, ed entrambi sono già visitati, quindi G viene estratto dalla pila.
- Allo stesso modo, anche E viene rimosso.
- Ora, il vertice B è in cima allo stack, il suo altro nodo (vertice) F è esplorato e memorizzato nello stack.
- Il vertice F ha due successori C e D, tra questi C viene prima attraversato e archiviato nello stack.
- Vertex C ha solo un predecessore che è già visitato, quindi viene rimosso dallo stack.
- Ora il vertice D connesso a F viene visitato e memorizzato nello stack.
- Poiché il vertice D non ha nodi non visitati, quindi D viene rimosso.
- Allo stesso modo, F, B e A sono anche spuntati.
- L'output generato è - A, B, E, G, F, C, D.
Le applicazioni di DFS includono l'ispezione di un grafico a due lati collegati, un grafico fortemente connesso, un grafico aciclico e un ordine topologico .
Un grafo è chiamato due spigoli collegati se e solo se rimane connesso anche se uno dei suoi spigoli viene rimosso. Questa applicazione è molto utile nelle reti di computer in cui l'errore di un collegamento nella rete non influisce sulla rete rimanente e sarebbe ancora connesso.
Un grafo fortemente connesso è un grafico in cui deve esistere un percorso tra la coppia ordinata di vertici. DFS è 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 sui vertici mentre DFS è un algoritmo basato su edge.
- La struttura dei dati della coda viene utilizzata in BFS. D'altra parte, DFS utilizza stack o ricorsione.
- Lo spazio di memoria viene efficientemente utilizzato in DFS mentre l'utilizzo dello spazio in BFS non è efficace.
- BFS è un algoritmo ottimale mentre DFS non è ottimale.
- DFS costruisce alberi stretti e lunghi. Come contro, BFS costruisce un 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 fornisce soluzioni più profonde e non è ottimale, ma funziona bene quando la soluzione è densa mentre BFS è ottimale e cerca inizialmente l'obiettivo ottimale.
