GeeksforGeeks

Breadth First Search

BFS sta per Breadth First Search è una tecnica basata sui vertici per trovare il percorso più breve nel grafico. Utilizza una struttura dati a coda che segue il first in first out. In BFS, un vertice viene selezionato alla volta quando viene visitato e segnato, poi i suoi adiacenti vengono visitati e memorizzati nella coda. È più lento di DFS.
Ex-

 A / \ B C / / \ D E F

Output è:

A, B, C, D, E, F

Depth First Search

DFS sta per Depth First Search è una tecnica basata sui bordi. Utilizza la struttura dati Stack, esegue due fasi, prima i vertici visitati vengono spinti nello stack e poi se non ci sono vertici allora i vertici visitati vengono eliminati.
Ex-

 A / \ B C / / \ D E F

Output è:

A, B, D, C, E, F

BFS vs DFS

S.NO	BFS	DFS
	BFS sta per Breadth First Search.	DFS sta per Depth First Search.
	BFS(Breadth First Search) usa la struttura dati Queue per trovare il percorso più breve.	DFS(Depth First Search) usa la struttura dati Stack.
	BFS può essere usato per trovare il percorso più breve di una singola fonte in un grafico non pesato, perché in BFS, raggiungiamo un vertice con il minimo numero di bordi da un vertice sorgente.	In DFS, potremmo attraversare più bordi per raggiungere un vertice di destinazione da una fonte.
	BFS è più adatto per cercare i vertici che sono più vicini alla fonte data.	DFS è più adatto quando ci sono soluzioni lontane dalla fonte.
	BFS considera prima tutti i vicini e quindi non è adatto agli alberi decisionali usati nei giochi o nei puzzle.	DFS è più adatto a problemi di gioco o puzzle. Prendiamo una decisione, poi esploriamo tutti i percorsi attraverso questa decisione. E se questa decisione porta a una situazione vincente, ci fermiamo.
	La complessità temporale di BFS è O(V + E) quando si usa la Adjacency List e O(V^2) quando si usa la Adjacency Matrix, dove V sta per vertici ed E sta per bordi.	La complessità temporale di DFS è anche O(V + E) quando viene usata la Adjacency List e O(V^2) quando viene usata la Adjacency Matrix, dove V sta per vertici ed E sta per bordi.

Si veda anche BFS vs DFS per Binary Tree per le differenze per un Binary Tree Traversal.