Die Hauptunterschied zwischen BFS und DFS ist das BFS oder Breadth First Search geht Ebene für Ebene weiter, während DFS oder Depth First Search einem Pfad vom Start- zum Endknoten folgt und dann von Anfang bis Ende zum anderen Pfad wechselt usw., bis alle Knoten besucht werden.

Ein Graph ist eine nichtlineare Datenstruktur, die Datenelemente als Netzwerkmodell anordnet. Knoten in einem Graphen werden Knoten genannt, und die Kanten verbinden diese Knoten. Es ist möglich, die meisten Graphenprobleme mit Suchmethoden zu lösen. Breadth First Search (BFS) und Depth First Search (DFS) sind gebräuchliche Suchmethoden. Kurz gesagt verwendet BFS eine Warteschlange, während DFS einen Stack verwendet.

BFS, DFS

Was ist BFS

BFS steht für Suche nach Atemzug. Es verwendet eine Warteschlange. Der Prozess ist wie folgt.

Ein Beispiel ist wie folgt.

Abbildung 1: BFS

Angenommen, der Startknoten im obigen Bild ist 1. Die mit 1 verbundenen Knoten sind 2 und 4. Wir können also 1, 2 und 4 in eine Warteschlange stellen. Die Ausgabe ist 1, 2, 4. Für 1 gibt es keine verbleibenden Scheitelpunkte. Daher können wir 1 aus der Warteschlange entfernen. Jetzt können wir zu 2 gehen. Die benachbarten Eckpunkte von 2 sind 3, 5 und 6. Somit können wir 3, 5 und 6 in die Warteschlange stellen. Die Ausgabe ist 1, 2, 4, 3, 6. Zusätzlich zu diesen drei Zahlen gibt es keine benachbarten Eckpunkte, die mit 2 verbunden sind. Wir können also 2 aus der Warteschlange entfernen. Gehen wir nun zu 4 über. Der einzige benachbarte Knoten zu 4 ist 6. Er wurde bereits besucht. Für 4 gibt es keine Eckpunkte mehr. Daher können wir 4 aus der Warteschlange entfernen. Sie müssen diesen Vorgang wiederholen, bis die Warteschlange leer ist. Es zeigt die Beendigung des Suchvorgangs an.

Was ist DFS

DFS steht für Tiefensuche. Der Prozess ist wie folgt.

Besuchen Sie den angrenzenden nicht besuchten Scheitelpunkt und markieren Sie ihn als besucht. Zeigen Sie es dann in der Ausgabe an und schieben Sie es in den Stack.

Wenn kein benachbarter Scheitelpunkt gefunden wird, öffne Scheitelpunkt aus dem Stapel.

Fahren Sie mit den obigen beiden Schritten fort, bis der Stapel leer ist.

Abbildung 2: DFS

Der Startknoten ist A. Er wird in den Stapel geschoben. Die benachbarten Eckpunkte sind B und E. Betrachten Sie B. Wir können B auf den Stapel schieben. Da es keine benachbarten Knoten zu B gibt, können wir B aus dem Stapel nehmen. Die Ausgabe ist A B. Der verbleibende benachbarte Knoten zu A ist E, also können wir E auf den Stack legen. Jetzt ist die Ausgabe A B E.

Da es keine benachbarten Knoten zu A gibt, können wir ‚A‘aus dem Stapel holen. Die benachbarten Knoten für E sind C und H. Betrachten Sie nun C. Wir können C auf den Stapel schieben. Die Ausgabe ist A B E C. Der Vorgang wird fortgesetzt, bis der Stack leer ist. Es beendet den Suchvorgang.

Unterschied zwischen BFS und DFS

Definition

BFS (Breadth First Search) ist ein Graph-Traversal-Algorithmus, der den Graphen vom Wurzelknoten aus durchquert und alle benachbarten Knoten untersucht. DFS (Depth first search) ist ein Algorithmus, der mit dem Anfangsknoten des Graphen beginnt und dann immer tiefer geht, bis der erforderliche Knoten oder der Knoten ohne Kinder gefunden wird. Dies ist also der Hauptunterschied zwischen BFS und DFS.

Lange Form

Während BFS für Breadth First Search steht, steht DFS für Depth First Search.

Methode zum Speichern von Knoten

Ein weiterer wesentlicher Unterschied zwischen BFS und DFS besteht darin, dass BFS Warteschlangen verwendet, während DFS Stack verwendet.

Speicherverbrauch

Traversierungsmethode

Die Übertragungsmethode ist ein weiterer Unterschied zwischen BFS und DFS. BFS konzentriert sich darauf, zuerst die ältesten nicht besuchten Scheitelpunkte zu besuchen, während DFS sich am Anfang darauf konzentriert, die Scheitelpunkte entlang der Kante zu besuchen.

Abschluss

BFS und DFS sind zwei Suchmethoden, um ein Element in einem Diagramm zu finden. Der Hauptunterschied zwischen BFS und DFS besteht darin, dass BFS Ebene für Ebene fortschreitet, während DFS einem Pfad vom Start- zum Endknoten folgt und dann von Anfang bis Ende zum anderen Pfad wechselt usw., bis alle Knoten besucht werden.

Referenz:

1. Suchalgorithmus für die Breite zuerst | Pseudocode | Einführung, Bildung 4u, 22. März 2018, hier verfügbar.2. Breitensuche zuerst | BFS-Beispiele |, Bildung 4u, 22. März 2018, hier verfügbar.3. Tiefensuchalgorithmus | Graph Traversal Algorithm |, Education 4u, 22. März 2018, hier verfügbar.4. „BFS-Algorithmus – Javatpoint.“ www.javatpoint.com, hier verfügbar.5. „DFS-Algorithmus – Javatpoint.“ www.javatpoint.com, hier verfügbar.