Unterschied zwischen BFS und DFS

Die Breitensuche (BFS) und die Tiefensuche (DFS) sind zwei wichtige Algorithmen für die Suche. Die Breitensuche startet ihre Suche ab dem ersten Knoten und bewegt sich dann über die Ebenen, die näher am Wurzelknoten liegen, während der Algorithmus für die Tiefensuche mit dem ersten Knoten beginnt und dann seinen Pfad bis zum Endknoten des jeweiligen Pfads abschließt. Beide Algorithmen durchlaufen während der Suche jeden Knoten. Für die beiden Algorithmen werden unterschiedliche Codes geschrieben, um den Verfahrvorgang auszuführen. Sie gelten auch als wichtige Suchalgorithmen in der Künstlichen Intelligenz.

In diesem Thema erfahren Sie mehr über BFS VS DFS.

Wie funktionieren BFS und DFS?

Der Wirkungsmechanismus beider Algorithmen wird im Folgenden anhand von Beispielen erläutert. Wenden Sie sich zum besseren Verständnis des verwendeten Ansatzes an diese.

Beispiel für die Breitensuche

  • Schritt 1: N1 ist der Wurzelknoten und beginnt von hier aus. N1 ist mit drei Knoten N2, N3 und N4 verbunden. Alle drei Knoten sind noch nicht besucht. Also starten wir bei N2 und speichern es in der Warteschlange. Die Warteschlange mit dem Namen Q enthält also nur N2.

F: N2

  • Schritt 2: Als nächstes ist der Knoten, der mit N1 verbunden ist, N3. Da wir den Knoten überquert oder besucht haben, speichern wir ihn in der Warteschlange. Die aktualisierte Warteschlange ist also

Q: N3, N2

  • Schritt 3: Als nächstes ist der Knoten, der mit dem Wurzelknoten verbunden ist, N4. Wir werden es in der Warteschlange speichern.

Q: N4, N3, N2

  • Schritt 4: Alle Knoten, die mit N1 verbunden sind, werden in der Warteschlange gespeichert. Nun entfernen wir N2 aus der Warteschlange nach dem First-in-First-Out-Prinzip (FIFO) und finden die Knoten, die mit N2 bzw. N5 verbunden sind. N5 wird nicht einmal besucht, daher speichern wir es in der Warteschlange.

Q: N5, N4, N3

  • Schritt 5: Alle Eckpunkte werden besucht, sodass wir die Knoten so lange aus der Warteschlange entfernen, bis sie leer sind.

Beispiel für die erste Suche nach Tiefe

  • Schritt 1: Wir beginnen mit N1 als Startknoten und speichern ihn in einem Stapel S. N1 ist mit drei benachbarten Knoten N2, N3 und N4 verbunden. Beginnend mit N2 (Sie können alphabetisch oder numerisch beginnen) werden wir dies in den Stapel legen.

S: N2 (oben), N1

  • Schritt 2: Nun sind die Nachbarknoten von N2 N1 und N5. Da N1 bereits im Stapel vorhanden ist, heißt das, dass es besucht wird, nehmen wir N5 und legen es in den Stapel S.

S: N5 (oben), N2, N1

  • Schritt 3: Nun sind die Nachbarknoten von N5 N3 und N4. Wir werden N3 starten und es in den Stapel legen.

S: N3 (oben), N5, N2, N1

Jetzt ist N3 mit N5 und N1 verbunden, die bereits im Stapel vorhanden sind, dh, sie werden besucht. Daher werden wir N3 nach dem Last-in-First-Out-Prinzip (LIFO) aus dem Stapel entfernen.

S: N5 (oben), N2, N1

  • Schritt 4: Nun setzen wir den letzten Knoten, auf den wir in der gesamten Überquerung von N4 nicht gestoßen sind, in den Stapel.

S: N4 (oben), N5, N2, N1

  • Schritt 5: Jetzt werden keine anderen Knoten ausgelassen, und wir prüfen im Stapel, ob mit den jeweiligen Knoten verbundene Knoten vorhanden sind, die nicht besucht werden. Wenn alle verbundenen Knoten besucht werden, werden die im Stapel vorhandenen Knoten entfernt. Zum Beispiel hat N4 keine Verbindungsknoten, die wir nicht überprüft haben, sodass wir sie aus dem Stapel entfernen. Ebenso können wir nach anderen Knoten suchen. Der Algorithmus stoppt, sobald der Stapel leer ist.

Head-to-Head-Vergleich zwischen BFS und DFS (Infografik)

Nachfolgend sind die sechs wichtigsten Unterschiede zwischen BFS und DFS aufgeführt

Hauptunterschiede zwischen BFS und DFS

Lassen Sie uns einige der wichtigsten Unterschiede zwischen BFS und DFS diskutieren

  • Die Breitensuche (Breadth-First Search, BFS) startet am Stammknoten und besucht alle an ihn angeschlossenen Knoten, während DFS am Stammknoten startet und den vollständigen Pfad vervollständigt, der an den Knoten angeschlossen ist.
  • BFS folgt dem Ansatz von Queue, während DFS dem Ansatz von Stack folgt.
  • Der in BFS verwendete Ansatz ist optimal, während der in DFS verwendete Prozess nicht optimal ist.
  • Wenn es unser Ziel ist, den kürzesten Weg zu finden, wird BFS gegenüber DFS bevorzugt.

BFS- und DFS-Vergleichstabelle

Lassen Sie uns den besten Vergleich zwischen BFS und DFS diskutieren

BFSDFS
Die vollständige Form von BFS ist die Breitensuche.Die vollständige Form von DFS ist Depth First Search
BFS soll die kürzeste Entfernung finden und beginnt beim ersten oder Stammknoten und bewegt sich über alle an den jeweiligen Knoten angeschlossenen Knoten. Sie können sich einen Überblick über den Funktionsmechanismus verschaffen, indem Sie das folgende Beispiel durchgehen.DFS folgt einem tiefenbasierten Ansatz und vervollständigt den vollständigen Pfad durch alle mit dem jeweiligen Knoten verbundenen Knoten. Sie können sich einen Überblick über den Funktionsmechanismus verschaffen, indem Sie das folgende Beispiel durchgehen.
Dies geschieht nach dem Queue-Prinzip, dem FIFO-Prinzip (First In First Out).Dies geschieht nach dem Stack-Prinzip, dem LIFO-Prinzip (Last In First Out).
Die Knoten, die mehrmals durchlaufen werden, werden aus der Warteschlange entfernt.Die besuchten Knoten werden in den Stapel eingefügt. Wenn später keine weiteren Knoten mehr zu besuchen sind, werden sie entfernt.
Es ist vergleichsweise langsamer als die Tiefensuche.Es ist schneller als der Breadth-First-Search-Algorithmus.
Die Speicherzuweisung ist mehr als der Algorithmus für die Tiefensuche.Die Speicherzuweisung ist vergleichsweise geringer als beim Breitensuchalgorithmus

Fazit

Es gibt viele Anwendungen, in denen die oben genannten Algorithmen als maschinelles Lernen oder zum Auffinden von Lösungen im Zusammenhang mit künstlicher Intelligenz usw. verwendet werden. Sie werden hauptsächlich in Diagrammen verwendet, um festzustellen, ob es sich um eine zweiteilige Lösung handelt oder nicht, um Zyklen oder Komponenten zu erkennen, die miteinander verbunden sind. Sie werden auch als wichtige Algorithmen beim Auffinden des Pfades oder der kürzesten Entfernung angesehen. Abhängig von den Anforderungen des Geschäfts können wir zwei Algorithmen verwenden. Die Breitensuche wird jedoch eher als eine optimale Methode als der Tiefensuchalgorithmus angesehen.

Empfohlene Artikel

Dies ist eine Anleitung zu BFS VS DFS. Hier diskutieren wir die Unterschiede zwischen BFS und DFS-Schlüsseln mit Infografiken und Vergleichstabellen. Sie können sich auch die folgenden Artikel ansehen, um mehr zu erfahren -

  1. BFS-Algorithmus
  2. TeraData gegen Oracle
  3. Big Data gegen Data Warehouse
  4. Big Data vs Apache Hadoop: Top 4-Vergleich, den Sie lernen müssen