se viene fornito un problema grafico come sappiamo se è necessario utilizzare l'algoritmo di bfs o dfs ??? o quando usiamo l'algoritmo dfs o l'algoritmo bfs. Quali sono le differenze ed i vantaggi di uno rispetto all'altro?Struttura dati grafici: DFS vs BFS?
BFS utilizzerà più memoria a seconda del fattore di diramazione ... tuttavia, BFS è un algoritmo completo ... nel senso che se lo si sta utilizzando per cercare qualcosa nella profondità più bassa possibile, BFS ti darà il soluzione ottimale. La complessità dello spazio BFS è O(b^d) ... il fattore di diramazione elevato alla profondità (può essere MOLTO di memoria).
DFS d'altra parte, è molto meglio sullo spazio, tuttavia potrebbe trovare una soluzione non ottimale. Significa, se stai solo cercando un percorso da un vertice all'altro, potresti trovare la soluzione subottimale (e fermarti lì) prima di trovare il percorso più breve. La complessità dello spazio DFS è O(|V|) ... il che significa che la maggior parte della memoria che può occupare è il percorso più lungo possibile.
Hanno la stessa complessità di tempo.
In termini di implementazione, BFS viene solitamente implementato con Queue, mentre DFS utilizza uno Stack.
prima le ricerche per i fratelli prima. la profondità prima ovviamente cerca prima i bambini. Quindi, immagino dipenda dal tipo di ricerca che stai cercando di fare. le ricerche di tipo di relazione tra campi probabilmente si prestano a bfs, dove gerarchico (alberi, cartelle, ranghi, ecc.) sarebbe più adatto come dfs.
Entrambi gli attraversamenti grafici promettono una cosa: una traversata completa del grafico, visitando ogni vertice nel grafico. Se non si dispone di contatori di memoria, DFS è una buona scelta, poiché BFS occupa molto spazio. Quindi, scegliere tra questi due dipende dal tuo fabbisogno.
Vuoi trovare i componenti (fortemente /) connessi del grafico? o risolvere il labirinto o il sudoku? Usa DFS. Se si guarda da vicino, Pre-Order, Post-Order e In-Order sono tutte varianti del DFS. Quindi, sì, sono alcune applicazioni interessanti.
BFS se si desidera verificare se un grafico è bipartito, trovare il percorso più breve tra due nodi o applicazioni che richiedono tali attività.
Nella coda bfs viene utilizzato mentre nello stack dfs viene utilizzato per memorizzare i vertici in base al traversal del grafico.
2- nel processo bfs viene eseguito da livello a livello (in base al grafico diretto o non diretto) mentre in dfs il processo viene eseguito in profondità (il processo di visitare prima il nodo radice e un altro è fare lontano e quindi applicare il backtracking da ultimo nodo al nodo radice).
BFS è estremamente buono per i percorsi più brevi mentre DFS non lo è.
Aggiungi ulteriori dettagli alla tua risposta. –
qual è la complessità del tempo? – Jony
La complessità temporale per entrambi è: O (b^d) ... il che significa che si basa sul fattore di diramazione e sulla profondità cercata. BFS e DFS hanno lo stesso peggior caso ... cercando l'intero albero. – Polaris878
Ecco un buon collegamento per commenti su quando è possibile utilizzare uno di essi. http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/ – DogEatDog