Wann ist es sinnvoll, die Depth-First-Suche (DFS) gegenüber der Breadth-First-Suche (BFS) zu verwenden?

Question

Ich verstehe die Unterschiede zwischen DFS und BFS, aber ich möchte wissen, wann es sinnvoller ist, das eine dem anderen vorzuziehen.

Kann jemand Beispiele dafür nennen, wie DFS den BFS übertrumpfen würde und umgekehrt?

Answer 1

Für BFS können wir das Beispiel Facebook betrachten. Wir erhalten Vorschläge zum Hinzufügen von Freunden aus dem FB-Profil von anderen Profilen anderer Freunde. Angenommen, A->B, während B->E und B->F, so A wird Vorschlag für E und F bekommen. Sie müssen BFS verwenden, um bis zur zweiten Ebene zu lesen. DFS basiert eher auf Szenarien, in denen wir etwas auf der Grundlage von Daten vorhersagen wollen, die wir von der Quelle bis zum Ziel haben. Wie bereits über Schach oder Sudoku erwähnt. Eine Sache, die ich hier anders sehe, ist, dass ich glaube, dass DFS für den kürzesten Weg verwendet werden sollte, weil DFS zuerst den gesamten Weg abdeckt und wir dann den besten entscheiden können. Aber da BFS den gierigen Ansatz verwendet, sieht es vielleicht so aus, als wäre es der kürzeste Weg, aber das Endergebnis könnte anders aussehen. Lassen Sie mich wissen, ob mein Verständnis falsch ist.

Answer 2

Entsprechend den Eigenschaften von DFS und BFS. Wenn wir zum Beispiel den kürzesten Weg finden wollen. verwenden wir in der Regel BFS, es kann den kürzesten Weg garantieren. aber dfs nur garantieren kann, dass wir von diesem Punkt kommen kann, dass Punkt zu erreichen, kann nicht garantieren, die "kürzeste".

Answer 3

Da bei der Depth-First-Suche ein Stack verwendet wird, während die Knoten verarbeitet werden, ist bei DFS ein Backtracking vorgesehen. Da bei der Breadth-First-Suche eine Warteschlange und kein Stapel verwendet wird, um zu verfolgen, welche Knoten verarbeitet werden, ist bei BFS kein Backtracking möglich.

Answer 4

Wenn die Breite des Baums sehr groß und die Tiefe gering ist, verwenden Sie DFS, da der Rekursionsstapel nicht überläuft, und wenn die Breite gering und die Tiefe sehr groß ist, verwenden Sie BFS, um den Baum zu durchlaufen.

Answer 5

Dies ist ein gutes Beispiel dafür, dass BFS in bestimmten Fällen besser ist als DFS. https://leetcode.com/problems/01-matrix/

Bei korrekter Umsetzung sollten beide Lösungen Zellen besuchen, die einen größeren Abstand als die aktuelle Zelle +1 haben. DFS ist jedoch ineffizient und besucht wiederholt dieselbe Zelle, was zu O(n*n) Komplexität führt.

Zum Beispiel,

1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
0,0,0,0,0,0,0,0,