Der Hauptunterschied zwischen BFS und DFS besteht darin, dass BFS Ebene für Ebene fortschreitet, während DFS zuerst einem Pfad vom Start- zum Endknoten (Scheitelpunkt), dann einem anderen Pfad vom Anfang zum Ende usw. folgt, bis alle Knoten besucht sind. Darüber hinaus verwendet BFS die Warteschlange zum Speichern der Knoten, während DFS den Stapel zum Durchlaufen der Knoten verwendet.
BFS und DFS sind die Durchlaufmethoden, die beim Durchsuchen eines Diagramms verwendet werden. Graph Traversal ist der Prozess des Besuchs aller Knoten des Graphen. Ein Graph ist eine Gruppe von Eckpunkten ‚V‘ und Kanten ‚E‘, die mit den Eckpunkten verbunden sind.
Inhalt: BFS Vs DFS
- Comparison Chart
- Definition
- Key Differences
- Conclusion
Comparison Chart
| Basis for comparison | BFS | DFS |
|---|---|---|
| Basic | Vertex-based algorithm | Edge-based algorithm |
| Data structure used to store the nodes | Queue | Stack |
| Memory consumption | Inefficient | Efficient |
| Structure der konstruierte Baum | Breit und kurz | Schmal und lang |
| Traversing Mode | Älteste nicht besuchte Eckpunkte werden zuerst untersucht. | Eckpunkte entlang der Kante werden am Anfang untersucht. |
| Optimalität | Optimal, um die kürzeste Entfernung zu finden, nicht in Kosten. | Nicht optimal |
| Anwendung | Untersucht den bipartiten Graphen, die verbundene Komponente und den kürzesten Pfad, der in einem Graphen vorhanden ist. | Untersucht zweikantig verbundene Graphen, stark verbundene Graphen, azyklische Graphen und topologische Ordnung. |
Definition von BFS
Die Breitensuche (BFS) ist die in Graphen verwendete Methode. Es verwendet eine Warteschlange zum Speichern der besuchten Scheitelpunkte. Bei dieser Methode liegt der Schwerpunkt auf den Scheitelpunkten des Diagramms, zuerst wird ein Scheitelpunkt ausgewählt, dann wird er besucht und markiert. Die Scheitelpunkte neben dem besuchten Scheitelpunkt werden dann nacheinander besucht und in der Warteschlange gespeichert.
In ähnlicher Weise werden die gespeicherten Scheitelpunkte dann einzeln behandelt und ihre benachbarten Scheitelpunkte werden besucht. Ein Knoten wird vollständig erkundet, bevor er einen anderen Knoten im Diagramm besucht, dh er durchläuft zuerst die flachsten unerforschten Knoten.
Beispiel
Wir haben einen Graphen, dessen Eckpunkte A, B, C, D, E, F, G sind. Die am Prozess beteiligten Schritte sind:
- Vertex A wird erweitert und in der Warteschlange gespeichert.
- Vertices B, D und G Nachfolger von A werden erweitert und in der Warteschlange gespeichert, während Vertex A entfernt wird.
- Jetzt wird B am vorderen Ende der Warteschlange entfernt und die Nachfolgepunkte E und F gespeichert.
- Vertex D befindet sich am vorderen Ende der Warteschlange wird entfernt, und sein verbundener Knoten F wird bereits besucht.
- Vertex G wird aus der Warteschlange entfernt und hat Nachfolger E, der bereits besucht wurde.
- Jetzt werden E und F aus der Warteschlange entfernt, und der Nachfolgepunkt C wird durchlaufen und in der Warteschlange gespeichert.
- Endlich wird auch C entfernt und die Warteschlange ist leer, was bedeutet, dass wir fertig sind.
- Die generierte Ausgabe ist – A, B, D, G, E, F, C.
Anwendungen
BFS kann nützlich sein, um festzustellen, ob das Diagramm Komponenten verbunden hat oder nicht. Und es kann auch zum Erkennen eines zweiteiligen Graphen verwendet werden.
Ein Graph ist bipartit, wenn die Scheitelpunkte des Graphen in zwei disjunkte Mengen geteilt sind; keine zwei benachbarten Scheitelpunkte würden sich in derselben Menge befinden. Eine andere Methode zum Überprüfen eines zweigeteilten Diagramms besteht darin, das Auftreten eines ungeraden Zyklus im Diagramm zu überprüfen. Ein bipartiter Graph darf keinen ungeraden Zyklus enthalten.
BFS ist auch besser bei der Suche nach dem kürzesten Weg in der Grafik könnte als Netzwerk gesehen werden.
Definition von DFS
Die DFS-Traversing-Methode (Depth First Search) verwendet den Stapel zum Speichern der besuchten Scheitelpunkte. DFS ist die kantenbasierte Methode und arbeitet rekursiv, wobei die Scheitelpunkte entlang eines Pfades (Kante) untersucht werden. Die Erkundung eines Knotens wird ausgesetzt, sobald ein anderer unerforschter Knoten gefunden wird und die tiefsten unerforschten Knoten gleichzeitig durchquert werden. DFS durchquert / besucht jeden Scheitelpunkt genau einmal und jede Kante wird genau zweimal überprüft.
Beispiel
Ähnlich wie bei BFS nehmen wir das gleiche Diagramm für die Durchführung von DFS-Operationen, und die beteiligten Schritte sind:
- Unter Berücksichtigung von A als Startscheitelpunkt, der untersucht und im Stapel gespeichert wird.
- B Der Scheitelpunkt von A wird im Stapel gespeichert.
- Vertex B haben zwei Nachfolger E und F, darunter alphabetisch E wird zuerst untersucht und im Stapel gespeichert.
- Der Nachfolger von Vertex E, d. h. G , wird im Stapel gespeichert.
- Scheitelpunkt G hat zwei verbundene Scheitelpunkte, und beide sind bereits besucht, sodass G aus dem Stapel entfernt wird.
- In ähnlicher Weise E s auch entfernt.
- Nun befindet sich der Scheitelpunkt B oben auf dem Stapel, sein anderer Knoten (Scheitelpunkt) F wird untersucht und im Stapel gespeichert.
- Vertex F hat zwei Nachfolger C und D , zwischen denen C zuerst durchlaufen und im Stapel gespeichert wird.
- Vertex C hat nur einen Vorgänger, der bereits besucht ist, also wird er vom Stapel entfernt.
- Jetzt wird der mit F verbundene Scheitelpunkt D besucht und im Stapel gespeichert.
- Da der Scheitelpunkt D keine nicht besuchten Knoten hat, wird D entfernt.
- In ähnlicher Weise werden auch F, B und A angezeigt.
- Die generierte Ausgabe ist – A, B, E, G, F, C, D.
Anwendung
Die Anwendungen von DFS umfassen die Inspektion von zwei kantenverbundenen Graphen, stark verbundenen Graphen, azyklischen Graphen und topologischer Ordnung.
Ein Graph wird genau dann als zwei Kanten bezeichnet, wenn er verbunden bleibt, auch wenn eine seiner Kanten entfernt wird. Diese Anwendung ist sehr nützlich in Computernetzwerken, in denen der Ausfall einer Verbindung im Netzwerk das verbleibende Netzwerk nicht beeinflusst und es weiterhin verbunden wäre.
Stark verbundener Graph ist ein Graph, in dem ein Pfad zwischen geordneten Eckpunkten vorhanden sein muss. DFS wird im gerichteten Graphen zum Suchen des Pfades zwischen jedem geordneten Scheitelpunktpaar verwendet. DFS kann Konnektivitätsprobleme leicht lösen.
Hauptunterschiede zwischen BFS und DFS
- BFS ist ein scheitelpunktbasierter Algorithmus, während DFS ein kantenbasierter Algorithmus ist.
- Die Warteschlangendatenstruktur wird in BFS verwendet. Auf der anderen Seite verwendet DFS Stack oder Rekursion.
- Speicherplatz wird in DFS effizient genutzt, während die Speicherplatznutzung in BFS nicht effektiv ist.
- BFS ist der optimale Algorithmus, während DFS nicht optimal ist.
- DFS konstruiert schmale und lange Bäume. Im Gegensatz dazu konstruiert BFS einen breiten und kurzen Baum.
Fazit
BFS und DFS, beide Graphsuchtechniken haben eine ähnliche Laufzeit, aber einen unterschiedlichen Platzbedarf, DFS benötigt linearen Raum, weil wir uns an einen einzelnen Pfad mit unerforschten Knoten erinnern müssen, während BFS jeden Knoten im Speicher hält.
DFS liefert tiefere Lösungen und ist nicht optimal, aber es funktioniert gut, wenn die Lösung dicht ist, während BFS optimal ist, was zuerst das optimale Ziel sucht.