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

Wenn Sie sich dieser Frage als Programmierer nähern, fällt ein Faktor auf: Wenn Sie eine Rekursion verwenden, dann ist die Tiefensuche Einfacher zu implementieren, da Sie keine zusätzliche Datenstruktur mit den noch zu erforschenden Knoten pflegen müssen.

Hier ist die Tiefensuche für einen 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(neighbor) # Visit each neighbor if not already visited

Wenn Informationen über "bereits besuchte Orte" in einer separaten Datenstruktur gespeichert werden:

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(neighbor, visited)             # then visit the neighbor
dfs(origin, set())

Im Gegensatz dazu müssen Sie bei der Breadth-First-Suche eine separate Datenstruktur für die Liste der noch zu besuchenden Knoten pflegen.

Answer 2

Ein wichtiger Vorteil von BFS ist, dass damit der kürzeste Weg zwischen zwei beliebigen Knoten in einem ungewichteten Graphen gefunden werden kann. Im Gegensatz dazu, können wir das DFS nicht für die gleiche .

Answer 3

Im Folgenden finden Sie eine umfassende Antwort auf Ihre Frage.

In einfachen Worten:

Der BFS-Algorithmus (Breadth First Search), dessen Name "Breadth" bedeutet, entdeckt alle Nachbarn eines Knotens über die Außenkanten des Knotens, dann entdeckt er die nicht besuchten Nachbarn der zuvor erwähnten Nachbarn über deren Außenkanten und so weiter, bis alle von der ursprünglichen Quelle erreichbaren Knoten besucht sind (wir können fortfahren und eine andere ursprüngliche Quelle nehmen, wenn es noch nicht besuchte Knoten gibt und so weiter). Deshalb kann es verwendet werden, um den kürzesten Weg (wenn es einen gibt) von einem Knoten (Ursprungsquelle) zu einem anderen Knoten zu finden, wenn die Gewichte der Kanten einheitlich sind.

Der Algorithmus Depth First Search (DFS), dessen Name "Tiefe" bedeutet, findet die nicht besuchten Nachbarn des zuletzt entdeckten Knotens x über seine Außenkanten. Wenn es keinen unbesuchten Nachbarn des Knotens x gibt, geht der Algorithmus zurück, um die unbesuchten Nachbarn des Knotens (über seine Out-Edges) zu entdecken, von dem aus der Knoten x entdeckt wurde, und so weiter, bis alle von der ursprünglichen Quelle erreichbaren Knoten besucht sind (wir können fortfahren und eine andere ursprüngliche Quelle nehmen, wenn es noch unbesuchte Knoten gibt, und so weiter).

Sowohl BFS als auch DFS können unvollständig sein. Ist beispielsweise der Verzweigungsfaktor eines Knotens unendlich oder sehr groß, so dass die Ressourcen (Speicher) nicht ausreichen (z. B. bei der Speicherung der als Nächstes zu entdeckenden Knoten), dann ist das BFS nicht vollständig, auch wenn der gesuchte Schlüssel nur wenige Kanten von der ursprünglichen Quelle entfernt sein kann. Dieser unendliche Verzweigungsfaktor kann auf die unendliche Auswahl (benachbarte Knoten) eines bestimmten Knotens zurückzuführen sein, der entdeckt werden soll. Wenn die Tiefe unendlich ist oder die Ressourcen (Speicher) sehr groß sind (z. B. beim Speichern der als nächstes zu entdeckenden Knoten), dann ist das DFS nicht vollständig, obwohl der gesuchte Schlüssel der dritte Nachbar der ursprünglichen Quelle sein kann. Diese unendliche Tiefe kann darauf zurückzuführen sein, dass es für jeden Knoten, den der Algorithmus entdeckt, mindestens eine neue Auswahl (Nachbarknoten) gibt, die zuvor nicht besucht wurde.

Daraus lässt sich schließen, wann das BFS und das DFS eingesetzt werden sollten. Angenommen, wir haben es mit einem überschaubaren begrenzten Verzweigungsfaktor und einer überschaubaren begrenzten Tiefe zu tun. Wenn der gesuchte Knoten oberflächlich ist, d.h. nach einigen Kanten von der ursprünglichen Quelle aus erreichbar ist, dann ist es besser, BFS zu verwenden. Ist der gesuchte Knoten hingegen tief, d.h. nach vielen Kanten von der ursprünglichen Quelle erreichbar, dann ist es besser, DFS zu verwenden.

Wenn wir z.B. in einem sozialen Netzwerk nach Personen suchen wollen, die ähnliche Interessen wie eine bestimmte Person haben, können wir BFS von dieser Person als Ursprungsquelle anwenden, da diese Personen meist seine direkten Freunde oder Freunde von Freunden sind, d.h. ein oder zwei Kanten weit entfernt. Wenn wir andererseits nach Personen suchen wollen, die völlig andere Interessen als eine bestimmte Person haben, können wir DFS von dieser Person als Ursprungsquelle verwenden, da diese Personen meist sehr weit von ihm entfernt sind, z.B. Freund von Freund von Freund...., d.h. zu viele Kanten weit entfernt.

Die Anwendungen von BFS und DFS können sich auch aufgrund des jeweiligen Suchmechanismus unterscheiden. Zum Beispiel können wir entweder BFS (unter der Annahme, dass der Verzweigungsfaktor überschaubar ist) oder DFS (unter der Annahme, dass die Tiefe überschaubar ist) verwenden, wenn wir nur die Erreichbarkeit von einem Knoten zu einem anderen überprüfen wollen, ohne Informationen darüber zu haben, wo dieser Knoten sein könnte. Auch können beide dieselben Aufgaben lösen, wie z.B. die topologische Sortierung eines Graphen (falls vorhanden). BFS kann verwendet werden, um den kürzesten Pfad mit einheitsgewichtigen Kanten von einem Knoten (ursprüngliche Quelle) zu einem anderen zu finden. DFS hingegen kann verwendet werden, um alle Möglichkeiten auszuschöpfen, da es in die Tiefe geht, z. B. um den längsten Weg zwischen zwei Knoten in einem azyklischen Graphen zu finden. DFS kann auch zur Erkennung von Zyklen in einem Graphen verwendet werden.

Bei unendlicher Tiefe und unendlichem Verzweigungsfaktor können wir schließlich die Iterative Vertiefungssuche (IDS) verwenden.

Answer 4

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 im Graphen (Baum, Martix auch als Graph behandeln) -> dfs ....

Answer 5

Einige Algorithmen sind auf bestimmte Eigenschaften von DFS (oder BFS) angewiesen, um zu funktionieren. Der Algorithmus von Hopcroft und Tarjan zum Auffinden von Komponenten mit zwei Verbindungen macht sich beispielsweise die Tatsache zunutze, dass jeder bereits besuchte Knoten, auf den das DFS trifft, auf dem Pfad von der Wurzel zum aktuell untersuchten Knoten liegt.