Non riesco a trovare una risposta a questo in linea, e in altre risposte a domande simili a questo sembra solo un dato di fatto che un vantaggio di DFS è che utilizza meno memoria di DFS.Perché una ricerca per ampiezza utilizza prima più memoria che profondità?
Per me questo sembra l'opposto di quello che mi aspetterei. Un BFS deve solo memorizzare l'ultimo nodo visitato. Per esempio, se stiamo cercando il numero 7 nella struttura sottostante:
cercherà il nodo con valore 8, poi 3, 10, 1, 6, 14, 4, quindi Finaly 7. Per un DFS cercherà il nodo con valore 8, quindi 3, 1, 6, 4 e infine 7.
Se ciascun nodo è archiviato nella memoria, con informazioni sul suo valore, i suoi figli e la posizione nell'albero quindi un programma BFS dovrà solo memorizzare le informazioni sulla posizione dell'ultimo nodo visitato, quindi controllare l'albero e trovare il prossimo nodo nell'albero. Un programma DFS deve memorizzare l'ultimo nodo in cui si trovava, così come tutti i nodi che ha già visitato, quindi non li controlla di nuovo e passa in rassegna tutti i nodi foglia che escono da uno dei nodi di seconda o ultima generazione.
Quindi perché un BFS utilizza effettivamente meno memoria?
Un albero completo sarà in genere più largo di quanto sia alto. Se il tuo albero di esempio fosse pieno, avresti 8 nodi al livello inferiore. In DFS, avresti bisogno solo di uno stack profondo quanto il livello più profondo. In BFS, hai bisogno di una coda larga quanto il livello più ampio. –
La complessità spaziale di DFS è O (d) dove d è il [diametro] (http://en.wikipedia.org/wiki/Distance_ (graph_theory) #Related_concepts) del grafico. Quello di BFS è O (w), dove w è il numero massimo di vertici che hanno la stessa distanza dal nodo iniziale. Dipende dalla struttura del grafo che dei due è più efficiente. –