wake-up-neo.net

Wann ist es sinnvoll, die Tiefensuche (DFS) und die Breitensuche (BFS) zu verwenden?

Ich verstehe die Unterschiede zwischen DFS und BFS, bin aber interessiert zu wissen, wann es praktischer ist, eine über die andere zu verwenden.

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

297
Parth

Dies hängt stark von der Struktur des Suchbaums und der Anzahl und Position der Lösungen (auch als gesuchte Elemente bezeichnet) ab.

  • Wenn Sie wissen, dass eine Lösung nicht weit von der Wurzel des Baums entfernt ist, ist eine Breitensuche (BFS) möglicherweise besser.
  • Wenn der Baum sehr tief ist und Lösungen selten sind, kann die Tiefensuche (DFS) sehr lange dauern, BFS kann jedoch schneller sein.

  • Wenn der Baum sehr breit ist, benötigt ein BFS möglicherweise zu viel Speicher, sodass dies möglicherweise völlig unpraktisch ist.

  • Wenn häufig Lösungen gefunden werden, diese sich jedoch tief im Baum befinden, kann BFS unpraktisch sein.

  • Wenn der Suchbaum sehr tief ist, müssen Sie die Suchtiefe für die erste Tiefensuche (DFS) ohnehin einschränken (z. B. mit iterativer Vertiefung).

Dies sind jedoch nur Faustregeln. Sie müssen wahrscheinlich experimentieren.

296

Tiefensuche

Tiefensuche wird häufig in Simulationen von Spielen (und spielerischen Situationen in der realen Welt) verwendet. In einem typischen Spiel können Sie eine von mehreren möglichen Aktionen auswählen. Jede Auswahl führt zu weiteren Auswahlmöglichkeiten, von denen jede zu weiteren Auswahlmöglichkeiten führt, und so weiter zu einem immer größer werdenden baumförmigen Diagramm von Möglichkeiten.

enter image description here

Zum Beispiel können Sie sich in Spielen wie Schach, Tic-Tac-Toe, wenn Sie sich für einen Zug entscheiden, mental einen Zug vorstellen, dann die möglichen Reaktionen Ihres Gegners, dann Ihre Reaktionen und so weiter. Sie können entscheiden, was zu tun ist, indem Sie sehen, welcher Zug zum besten Ergebnis führt.

Nur einige Pfade in einem Spielbaum führen zu Ihrem Gewinn. Einige führen zu einem Sieg Ihres Gegners. Wenn Sie ein solches Ende erreichen, müssen Sie zu einem vorherigen Knoten zurückkehren oder einen anderen Weg beschreiten. Auf diese Weise erkunden Sie den Baum, bis Sie einen Pfad mit einem erfolgreichen Abschluss finden. Dann machen Sie den ersten Schritt auf diesem Weg.


Breitensuche

Die Breitensuche hat eine interessante Eigenschaft: Sie findet zuerst alle Scheitelpunkte, die eine Kante vom Startpunkt entfernt sind, dann alle Scheitelpunkte, die zwei Kanten entfernt sind, und so weiter. Dies ist nützlich, wenn Sie versuchen, den kürzesten Weg vom Startscheitelpunkt zu einem bestimmten Scheitelpunkt zu finden. Sie starten ein BFS. Wenn Sie den angegebenen Scheitelpunkt finden, wissen Sie, dass der Pfad, den Sie bisher verfolgt haben, der kürzeste Pfad zum Knoten ist. Wenn es einen kürzeren Pfad gäbe, hätte das BFS ihn bereits gefunden.

Die Breitensuche kann zum Auffinden der Nachbarknoten in Peer-to-Peer-Netzwerken wie BitTorrent, GPS-Systemen zum Auffinden von Standorten in der Nähe, sozialen Netzwerken zum Auffinden von Personen in der angegebenen Entfernung und dergleichen verwendet werden.

121

Nette Erklärung von http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/

Ein Beispiel für BFS

Hier ist ein Beispiel, wie ein BFS aussehen würde. Dies ist so etwas wie Level Order Tree Traversal, bei dem wir QUEUE mit ITERATIVE-Ansatz verwenden (meistens wird RECURSION mit DFS enden). Die Zahlen geben die Reihenfolge an, in der auf die Knoten in einem BFS zugegriffen wird:

enter image description here

Bei einer eingehenden ersten Suche beginnen Sie am Stamm und folgen einem der Zweige des Baums so weit wie möglich, bis entweder der gesuchte Knoten gefunden wurde oder Sie auf einen Blattknoten (einen Knoten ohne untergeordnete Knoten) stoßen. Wenn Sie auf einen Blattknoten stoßen, setzen Sie die Suche beim nächsten Vorfahren mit unerforschten Kindern fort.

Ein Beispiel für DFS

Hier ist ein Beispiel, wie ein DFS aussehen würde. Ich denke, dass das Durchlaufen der Post-Order im Binärbaum zuerst mit der Arbeit ab der Ebene Leaf beginnt. Die Zahlen geben die Reihenfolge an, in der auf die Knoten in einem DFS zugegriffen wird:

enter image description here

Unterschiede zwischen DFS und BFS

Im Vergleich zu BFS und DFS besteht der große Vorteil von DFS darin, dass der Speicherbedarf viel geringer ist als bei BFS, da nicht alle untergeordneten Zeiger auf jeder Ebene gespeichert werden müssen. Abhängig von den Daten und dem, wonach Sie suchen, kann entweder DFS oder BFS vorteilhaft sein.

Wenn Sie beispielsweise bei einem Stammbaum nach jemandem suchen, der noch am Leben ist, können Sie davon ausgehen, dass sich diese Person am Ende des Baumes befindet. Dies bedeutet, dass ein BFS sehr lange braucht, um dieses letzte Niveau zu erreichen. Eine DFS würde das Ziel jedoch schneller finden. Wenn man jedoch nach einem Familienmitglied suchen würde, das vor langer Zeit gestorben ist, wäre diese Person näher an der Spitze des Baumes. Dann wäre ein BFS normalerweise schneller als ein DFS. Die Vorteile hängen von den Daten und dem gesuchten Objekt ab.

Ein weiteres Beispiel ist Facebook; Vorschlag für Freunde von Freunden. Wir brauchen unmittelbare Freunde für Vorschläge, wo wir BFS verwenden können. Möglicherweise können wir den kürzesten Pfad finden oder den Zyklus ermitteln (mithilfe von Rekursion) und DFS verwenden.

102

Die Breitensuche ist im Allgemeinen die beste Methode, wenn die Tiefe des Baums variieren kann und Sie nur einen Teil des Baums nach einer Lösung durchsuchen müssen. Der kürzeste Weg von einem Startwert zu einem Endwert ist beispielsweise ein guter Ort, um BFS zu verwenden.

Die Tiefensuche wird häufig verwendet, wenn Sie den gesamten Baum durchsuchen müssen. Es ist einfacher zu implementieren (mithilfe von Rekursion) als BFS und erfordert weniger Status: Während für BFS das Speichern der gesamten Grenze erforderlich ist, müssen Sie in DFS nur die Liste der übergeordneten Knoten des aktuellen Elements speichern.

34
Nick Johnson

DFS ist platzsparender als BFS, kann jedoch zu unnötigen Tiefen führen.

Ihre Namen sind aufschlussreich: Wenn es eine große Breite (d. H. Einen großen Verzweigungsfaktor), aber eine sehr begrenzte Tiefe (z. B. eine begrenzte Anzahl von "Zügen") gibt, ist DFS BFS vorzuziehen.


Auf IDDFS

Es sollte erwähnt werden, dass es eine weniger bekannte Variante gibt, die die Speichereffizienz von DFS kombiniert, aber (kummulativ) die Besuchsreihenfolge von BFS ist, die iterative vertiefende Tiefensuche zuerst . Dieser Algorithmus überprüft einige Knoten erneut, trägt jedoch nur einen konstanten Faktor der asymptotischen Differenz bei.

23

Wenn Sie sich dieser Frage als Programmierer nähern, fällt ein Faktor auf: Wenn Sie die Rekursion verwenden, ist die Tiefensuche einfacher zu implementieren, da Sie keine zusätzliche Datenstruktur pflegen müssen Enthält die Knoten, die noch zu erkunden sind.

Hier ist die Tiefensuche nach einem nicht-orientierten Graphen, wenn Sie bereits besuchte Informationen in den Knoten speichern:

def dfs(Origin):                               # DFS from Origin:
    Origin.visited = True                      # Mark the Origin as visited
    for neighbor in Origin.neighbors:          # Loop over the neighbors
        if not neighbor.visited: dfs(next)     # Visit each neighbor if not already visited

Wenn Sie bereits besuchte Informationen in einer separaten Datenstruktur speichern:

def dfs(node, visited):                        # DFS from Origin, with already-visited set:
    visited.add(node)                          # Mark the Origin as visited
    for neighbor in node.neighbors:            # Loop over the neighbors
        if not neighbor in visited:            # If the neighbor hasn't been visited yet,
            dfs(node, visited)                 # then visit the neighbor
dfs(Origin, set())

Vergleichen Sie dies mit der Breitensuche, bei der Sie eine separate Datenstruktur für die Liste der noch zu besuchenden Knoten benötigen, egal was passiert.

12
Gilles

Ein wichtiger Vorteil von BFS wäre, dass damit der kürzeste Weg zwischen zwei beliebigen Knoten in einem ungewichteten Graphen gefunden werden kann. Wobei wir können DFS nicht für dasselbe verwenden .

12

Für BFS können wir Facebook als Beispiel betrachten. Wir erhalten den Vorschlag, Freunde aus dem FB-Profil von anderen Profilfreunden hinzuzufügen. Angenommen, A-> B, während B-> E und B-> F, so wird A Vorschläge für E und F erhalten. Sie müssen BFS verwenden, um bis zur zweiten Ebene zu lesen. DFS basiert mehr auf Szenarien, in denen wir etwas basierend auf Daten prognostizieren möchten, die wir von der Quelle bis zum Ziel haben. Wie schon erwähnt über Schach oder Sudoku. Ich bin der Meinung, dass DFS für den kürzesten Pfad verwendet werden sollte, da DFS zuerst den gesamten Pfad abdeckt und wir dann über den besten entscheiden können. Da BFS jedoch den Ansatz von Greedy verwendet, scheint dies der kürzeste Weg zu sein, aber das Endergebnis kann davon abweichen. Lassen Sie mich wissen, ob mein Verständnis falsch ist.

6
user2056463

Einige Algorithmen hängen von bestimmten Eigenschaften von DFS (oder BFS) ab, um zu funktionieren. Beispielsweise nutzt der Hopcroft- und Tarjan-Algorithmus zum Auffinden von 2 verbundenen Komponenten die Tatsache, dass sich jeder bereits besuchte Knoten, auf den DFS stößt, auf dem Pfad vom Stamm zum aktuell untersuchten Knoten befindet.

4
Rafał Dowgird

Entsprechend den Eigenschaften von DFS und BFS. Zum Beispiel, wenn wir den kürzesten Weg finden wollen. wir benutzen normalerweise bfs, es kann das 'kürzeste' garantieren. aber dfs kann nur garantieren, dass wir von diesem Punkt kommen können, kann diesen Punkt erreichen, kann nicht die "kürzeste" garantieren.

2
yeuyanglou

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

1
nil96

Ich denke, es hängt davon ab, mit welchen Problemen Sie konfrontiert sind.

  1. kürzester Weg auf einfachem Graphen -> bfs
  2. alle möglichen Ergebnisse -> dfs
  3. suche nach graph (behandle tree, martix auch als graph) -> dfs ....
1
BenDan

Da bei Tiefensuchen ein Stapel verwendet wird, während die Knoten verarbeitet werden, wird die Rückverfolgung mit DFS bereitgestellt. Da bei der Breitensuche eine Warteschlange und kein Stapel verwendet wird, um zu verfolgen, welche Knoten verarbeitet werden, wird die Rückverfolgung nicht mit BFS bereitgestellt.

1

Das Folgende ist eine umfassende Antwort auf Ihre Fragen.

In einfachen Worten:

Der BFS-Algorithmus (Breadth First Search) erkennt ab dem Namen "Breadth" alle Nachbarn eines Knotens durch die Außenkanten des Knotens und erkennt dann die nicht besuchten Nachbarn der zuvor erwähnten Nachbarn durch ihre Außenkanten usw. bis zu allen Die Knoten, die von der ursprünglichen Quelle aus erreichbar sind, werden besucht (wir können fortfahren und eine andere ursprüngliche Quelle nehmen, wenn es noch nicht besuchte Knoten usw. gibt). Aus diesem Grund kann der kürzeste Weg (falls vorhanden) von einem Knoten (ursprüngliche Quelle) zu einem anderen Knoten ermittelt werden, wenn die Kanten gleichmäßig gewichtet sind.

Der DFS-Algorithmus (Depth First Search) erkennt ausgehend von seinem Namen "Depth" die nicht besuchten Nachbarn des zuletzt entdeckten Knotens x durch seine Außenkanten. Wenn es keinen nicht besuchten Nachbarn vom Knoten x gibt, führt der Algorithmus eine Rückverfolgung durch, um die nicht besuchten Nachbarn des Knotens (durch seine Außenkanten) zu ermitteln, von dem aus Knoten x ermittelt wurde, usw., bis alle von der ursprünglichen Quelle aus erreichbaren Knoten besucht werden (Wir können fortfahren und eine andere ursprüngliche Quelle nehmen, wenn es noch nicht besuchte Knoten usw. gibt.).

Sowohl BFS als auch DFS können unvollständig sein. Wenn beispielsweise der Verzweigungsfaktor eines Knotens unendlich ist oder die zu unterstützenden Ressourcen (Speicher) sehr groß sind (z. B. beim Speichern der als Nächstes zu entdeckenden Knoten), ist das BFS nicht vollständig, obwohl sich der gesuchte Schlüssel in einiger Entfernung befinden kann wenige Kanten von der ursprünglichen Quelle. Dieser unendliche Verzweigungsfaktor kann aufgrund von unendlichen Auswahlmöglichkeiten (benachbarte Knoten) von einem bestimmten Knoten entdeckt werden. Wenn die Tiefe unendlich oder für die zu unterstützenden Ressourcen (Speicher) sehr groß ist (z. B. beim Speichern der als Nächstes zu entdeckenden Knoten), ist DFS nicht vollständig, obwohl der gesuchte Schlüssel der dritte Nachbar der ursprünglichen Quelle sein kann. Diese unendliche Tiefe kann auf eine Situation zurückzuführen sein, in der für jeden Knoten, den der Algorithmus entdeckt, mindestens eine neue Auswahl (benachbarter Knoten) vorhanden ist, die zuvor nicht besucht wurde.

Daher können wir schließen, wann BFS und DFS verwendet werden sollen. Angenommen, wir haben es mit einem überschaubaren, begrenzten Verzweigungsfaktor und einer überschaubaren, begrenzten Tiefe zu tun. Wenn der gesuchte Knoten flach ist, d. H. Nach einigen Kanten von der ursprünglichen Quelle erreichbar ist, ist es besser, BFS zu verwenden. Wenn der gesuchte Knoten andererseits tief ist, d. H. Nach vielen Kanten von der ursprünglichen Quelle erreichbar ist, ist es besser, DFS zu verwenden.

Wenn wir zum Beispiel in einem sozialen Netzwerk nach Personen suchen möchten, die ähnliche Interessen einer bestimmten Person haben, können wir BFS von dieser Person als ursprüngliche Quelle verwenden, da es sich meistens um seine direkten Freunde oder Freunde von Freunden handelt oder zwei Kanten weit. Wenn wir dagegen nach Personen suchen möchten, die ganz andere Interessen einer bestimmten Person haben, können wir die DFS dieser Person als ursprüngliche Quelle verwenden, da diese Personen meistens sehr weit von ihr entfernt sind, dh Freund eines Freundes eines Freundes .... also zu viele Kanten weit.

Die Anwendungen von BFS und DFS können auch aufgrund des Suchmechanismus in jedem einzelnen variieren. Zum Beispiel können wir entweder BFS (vorausgesetzt, der Verzweigungsfaktor ist verwaltbar) oder DFS (vorausgesetzt, die Tiefe ist verwaltbar) verwenden, wenn wir nur die Erreichbarkeit von einem Knoten zu einem anderen überprüfen möchten, ohne Informationen darüber zu haben, wo sich dieser Knoten befinden kann. Außerdem können beide dieselben Aufgaben wie das topologische Sortieren eines Graphen (falls vorhanden) lösen. BFS kann verwendet werden, um den kürzesten Weg mit Kanten des Einheitsgewichts von einem Knoten (ursprüngliche Quelle) zu einem anderen zu finden. Während DFS verwendet werden kann, um alle Auswahlmöglichkeiten aufgrund der Art der Vertiefung zu erschöpfen, z. B. um den längsten Pfad zwischen zwei Knoten in einem azyklischen Diagramm zu ermitteln. Auch DFS kann zur Zykluserkennung in einem Diagramm verwendet werden.

Wenn wir eine unendliche Tiefe und einen unendlichen Verzweigungsfaktor haben, können wir die Iterative Deepening Search (IDS) verwenden.

1
Mosab Shaheen

Es hängt von der Situation ab, in der es verwendet wird. Wann immer wir ein Problem beim Durchlaufen eines Graphen haben, tun wir es aus irgendeinem Grund. Wenn es ein Problem gibt, den kürzesten Pfad in einem ungewichteten Diagramm zu finden oder zu ermitteln, ob ein Diagramm zweiteilig ist, können wir BFS verwenden. Bei Problemen mit der Zykluserkennung oder einer Logik, die ein Backtracking erfordert, können wir DFS verwenden.

0
ankur314

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

Bei korrekter Implementierung 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,
0
coderek