BFS vs. DFS – Unterschied zwischen ihnen

Was ist BFS?

BFS ist ein Algorithmus, der zum Zeichnen von Daten, zum Durchsuchen von Bäumen oder zum Durchlaufen von Strukturen verwendet wird. Der Algorithmus besucht und markiert effizient und in genauer Breite alle wichtigen Knoten in einem Diagramm.

Dieser Algorithmus wählt einen einzelnen Knoten (Anfangs- oder Quellpunkt) in einem Diagramm aus und besucht dann alle Knoten, die neben dem ausgewählten Knoten liegen. Sobald der Algorithmus den Startknoten besucht und markiert hat, bewegt er sich zu den nächsten, noch nicht besuchten Knoten und analysiert diese.

Nach dem Besuch werden alle Knoten markiert. Diese Iterationen werden fortgesetzt, bis alle Knoten des Diagramms erfolgreich besucht und markiert wurden. Die vollständige Form von BFS ist die Breitensuche.

Was ist DFS?

DFS ist ein Algorithmus zum Suchen oder Durchqueren von Diagrammen oder Bäumen in Tiefenrichtung. Die Ausführung des Algorithmus beginnt am Wurzelknoten und erkundet jeden Zweig, bevor er zurückverfolgt wird. Es verwendet eine Stapeldatenstruktur, um sich zu merken, den nachfolgenden Scheitelpunkt abzurufen und eine Suche zu starten, wann immer in einer Iteration eine Sackgasse auftritt. Die vollständige Form von DFS ist die Tiefensuche.

Unterschied zwischen BFS- und DFS-Binärbaum

Hier sind die wichtigen Unterschiede zwischen BFS und DFS.

BFS	DFS
BFS findet den kürzesten Weg zum Ziel.	DFS geht zum Ende eines Teilbaums und kehrt dann zurück.
Die vollständige Form von BFS ist die Breitensuche.	Die vollständige Form von DFS ist Depth First Search.
Es verwendet eine Warteschlange, um den nächsten zu besuchenden Ort zu verfolgen.	Es verwendet einen Stapel, um den nächsten zu besuchenden Ort zu verfolgen.
BFS durchläuft die Baumebene.	DFS durchquert entsprechend der Baumtiefe.
Es wird mithilfe einer FIFO-Liste implementiert.	Es wird mithilfe der LIFO-Liste implementiert.
Im Vergleich zu DFS ist mehr Speicher erforderlich.	Es benötigt im Vergleich zu BFS weniger Speicher.
Dieser Algorithmus liefert die flachste Pfadlösung.	Dieser Algorithmus garantiert nicht die flachste Pfadlösung.
In BFS ist kein Backtracking erforderlich.	Es besteht die Notwendigkeit eines Backtrackings im DFS.
Sie können niemals in endlichen Schleifen gefangen sein.	Sie können in Endlosschleifen gefangen sein.
Wenn Sie kein Ziel finden, müssen Sie möglicherweise viele Knoten erweitern, bevor die Lösung gefunden wird.	Wenn Sie kein Ziel finden, kann es zu einem Backtracking des Blattknotens kommen.

Beispiel für BFS

Im folgenden BFS-Beispiel haben wir einen Graphen mit 6 Knoten verwendet.

Beispiel für BFS

Schritt 1)

Sie haben ein Diagramm mit sieben Zahlen im Bereich von 0 bis 6.

Schritt 2)

0 oder Null wurde als Wurzelknoten markiert.

Schritt 3)

0 wird besucht, markiert und in die Warteschlangendatenstruktur eingefügt.

Schritt 4)

Die verbleibenden 0 benachbarten und nicht besuchten Knoten werden besucht, markiert und in die Warteschlange eingefügt.

Schritt 5)

Durchlaufiterationen werden wiederholt, bis alle Knoten besucht sind.

Beispiel für DFS

Im folgenden DFS-Beispiel haben wir einen ungerichteten Graphen mit 5 Knoten verwendet.

Schritt 1)

Wir haben mit Knoten 0 begonnen. Der Algorithmus beginnt damit, ihn in die besuchte Liste aufzunehmen und gleichzeitig alle seine benachbarten Knoten in die Datenstruktur namens Stapel.

Schritt 2)

Sie besuchen das Element, das sich oben im Stapel befindet, zum Beispiel 1, und gehen zu den angrenzenden Knoten. Dies liegt daran, dass 0 bereits besucht wurde. Daher besuchen wir Scheitelpunkt 2.

Schritt 3)

Scheitelpunkt 2 hat einen nicht besuchten nahegelegenen Scheitelpunkt in 4. Deshalb fügen wir diesen zum Stapel hinzu und besuchen ihn.

Schritt 4)

Schließlich besuchen wir den letzten Scheitelpunkt 3, er hat keine unbesuchten angrenzenden Knoten. Wir haben die Durchquerung des Diagramms mit dem DFS-Algorithmus abgeschlossen.

Anwendungen von BFS

Hier sind Anwendungen von BFS:

Ungewichtete Diagramme

Der BFS-Algorithmus kann problemlos den kürzesten Pfad und einen minimalen Spannbaum erstellen, um alle Eckpunkte des Diagramms in kürzester Zeit und mit hoher Genauigkeit zu besuchen.

P2P-Netzwerke

BFS kann implementiert werden, um alle nächsten oder benachbarten Knoten in einem Peer-to-Peer-Netzwerk zu lokalisieren. Dadurch werden die erforderlichen Daten schneller gefunden.

Web-Crawler

Suchmaschinen oder Webcrawler können durch den Einsatz von BFS problemlos mehrere Indexebenen erstellen. Die BFS-Implementierung beginnt bei der Quelle, also der Webseite, und besucht dann alle Links von dieser Quelle.

Netzwerkübertragung

Ein gesendetes Paket wird vom BFS-Algorithmus geleitet, um alle Knoten zu finden und zu erreichen, für die es die Adresse hat.

Anwendungen von DFS

Hier sind wichtige Anwendungen von DFS:

Gewichtetes Diagramm

In einem gewichteten Diagramm generiert die DFS-Diagrammdurchquerung den kürzesten Pfadbaum und den minimalen Spannbaum.

Erkennen eines Zyklus in einem Diagramm

Ein Graph hat einen Zyklus, wenn wir während der DFS eine Hinterkante gefunden haben. Daher sollten wir DFS für das Diagramm ausführen und auf Hinterkanten prüfen.

Wegfindung

Wir können uns auf den DFS-Algorithmus spezialisieren, um einen Pfad zwischen zwei Eckpunkten zu suchen.

Topologische Sortierung

Es wird hauptsächlich zum Planen von Jobs aus den gegebenen Abhängigkeiten innerhalb der Jobgruppe verwendet. In der Informatik wird es bei der Befehlsplanung, Datenserialisierung, Logiksynthese und zum Bestimmen der Reihenfolge von Kompilierungsaufgaben verwendet.

Suche nach stark verbundenen Komponenten eines Graphen

Es wird im DFS-Diagramm verwendet, wenn es einen Pfad von jedem einzelnen Scheitelpunkt im Diagramm zu anderen verbleibenden Scheitelpunkten gibt.

Rätsel mit nur einer Lösung lösen

Der DFS-Algorithmus kann leicht angepasst werden, um alle Lösungen eines Labyrinths zu durchsuchen, indem Knoten auf dem vorhandenen Pfad in die besuchte Menge einbezogen werden.