Was ist BFS?
BFS ist ein Algorithmus, der zum Zeichnen von Daten oder zum Suchen von Bäumen oder zum Durchlaufen von Strukturen verwendet wird. Der Algorithmus besucht und markiert effizient alle Schlüsselknoten in einem Diagramm in einer genauen Breite.
Dieser Algorithmus wählt einen einzelnen Knoten (Anfangs- oder Quellpunkt) in einem Diagramm aus und besucht dann alle Knoten neben dem ausgewählten Knoten. Sobald der Algorithmus den Startknoten besucht und markiert, bewegt er sich zu den nächsten 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.
In diesem BSF Vs. DFS Binärbaum Tutorial, lernen Sie:
- Was ist BFS?
- Was ist DFS?
- Beispiel für BFS
- Beispiel für DFS
- Unterschied zwischen BFS- und DFS-Binärbaum
- Anwendungen von BFS
- Anwendungen der DFS
Was ist DFS?
DFS ist ein Algorithmus zum Finden oder Durchlaufen von Graphen oder Bäumen in Tiefenrichtung. Die Ausführung des Algorithmus beginnt am Wurzelknoten und untersucht jeden Zweig vor dem Zurückverfolgen. Es verwendet eine Stapeldatenstruktur, um sich zu merken, den nachfolgenden Scheitelpunkt abzurufen und eine Suche zu starten, wenn in einer Iteration eine Sackgasse auftritt. Die vollständige Form der DFS ist die Tiefensuche.
Beispiel für BFS
Im folgenden Beispiel für DFS haben wir ein Diagramm mit 6 Eckpunkten verwendet.
Beispiel für BFS
Schritt 1)
Sie haben eine Grafik mit sieben Zahlen zwischen 0 und 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)
Durchlaufende Iterationen werden wiederholt, bis alle Knoten besucht sind.
Beispiel für DFS
Im folgenden Beispiel für DFS haben wir einen ungerichteten Graphen mit 5 Eckpunkten verwendet.
Schritt 1)
Wir haben mit Scheitelpunkt 0 begonnen. Der Algorithmus beginnt damit, ihn in die besuchte Liste aufzunehmen und gleichzeitig alle benachbarten Scheitelpunkte in die als Stapel bezeichnete Datenstruktur einzufügen.
Schritt 2)
Sie besuchen das Element, das sich oben im Stapel befindet, z. B. 1, und gehen zu den benachbarten Knoten. Dies liegt daran, dass 0 bereits besucht wurde. Daher besuchen wir Vertex 2.
Schritt 3)
Scheitelpunkt 2 hat in 4 einen nicht besuchten Scheitelpunkt in der Nähe. Daher fügen wir diesen in den Stapel ein und besuchen ihn.
Schritt 4)
Schließlich werden wir den letzten Scheitelpunkt 3 besuchen, er hat keine nicht besuchten benachbarten Knoten. Wir haben die Durchquerung des Graphen mit dem DFS-Algorithmus abgeschlossen.
Unterschied zwischen BFS- und DFS-Binärbaum
| BFS | DFS |
| BFS findet den kürzesten Weg zum Ziel. | DFS geht zum Ende eines Teilbaums und geht 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 wird entsprechend der Baumebene durchlaufen. | Die DFS wird entsprechend der Baumtiefe durchlaufen. |
| Es wird mithilfe der FIFO-Liste implementiert. | Es wird mithilfe der LIFO-Liste implementiert. |
| Im Vergleich zu DFS ist mehr Speicher erforderlich. | Im Vergleich zu BFS wird weniger Speicher benötigt. |
| Dieser Algorithmus liefert die Lösung mit dem flachsten Pfad. | Dieser Algorithmus garantiert nicht die Lösung mit dem flachsten Pfad. |
| In BFS ist kein Backtracking erforderlich. | In der DFS ist ein Backtracking erforderlich. |
| 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 das Zurückverfolgen des Blattknotens auftreten. |
Anwendungen von BFS
Hier sind Anwendungen von BFS:
Ungewichtete Grafiken:
Der BFS-Algorithmus kann auf einfache Weise den kürzesten Pfad und einen minimalen Spannbaum erstellen, um alle Scheitelpunkte des Diagramms in kürzester Zeit 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.
Webcrawler:
Suchmaschinen oder Webcrawler können mithilfe von BFS problemlos mehrere Indexebenen erstellen. Die BFS-Implementierung beginnt bei der Quelle, 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 der DFS
Hier sind wichtige Anwendungen von DFS:
Gewichteter Graph:
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 die Hinterkanten überprü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 angegebenen Abhängigkeiten innerhalb der Jobgruppe verwendet. In der Informatik wird es bei der Befehlsplanung, Datenserialisierung, Logiksynthese und Bestimmung der Reihenfolge von Kompilierungsaufgaben verwendet.
Suche nach stark verbundenen Komponenten eines Diagramms:
Es wird im DFS-Diagramm verwendet, wenn ein Pfad von jedem Scheitelpunkt im Diagramm zu anderen verbleibenden Scheitelpunkten vorhanden ist.
Rätsel lösen mit nur einer Lösung:
Der DFS-Algorithmus kann leicht angepasst werden, um alle Lösungen für ein Labyrinth zu suchen, indem Knoten auf dem vorhandenen Pfad in die besuchte Menge aufgenommen werden.
WICHTIGE UNTERSCHIEDE:
- BFS findet den kürzesten Weg zum Ziel, während DFS zum Ende eines Teilbaums geht und dann zurückverfolgt.
- Die vollständige Form von BFS ist die Breitensuche, während die vollständige Form der DFS die Tiefensuche ist.
- BFS verwendet eine Warteschlange, um den nächsten zu besuchenden Ort zu verfolgen. Während DFS einen Stapel verwendet, um den nächsten zu besuchenden Standort zu verfolgen.
- BFS wird gemäß der Baumebene durchlaufen, während DFS gemäß der Baumtiefe durchlaufen wird.
- BFS wird unter Verwendung der FIFO-Liste implementiert, während DFS unter Verwendung der LIFO-Liste implementiert wird.
- In BFS können Sie niemals in endlichen Schleifen gefangen sein, während Sie in DFS in Endlosschleifen gefangen sein können.