Unterschied zwischen BFS und DFS

BFS vs DFS

Breitensuche (auch als BFS bekannt) ist eine Suchmethode, mit der alle Knoten eines bestimmten Graphen erweitert werden. Diese Aufgabe wird dadurch gelöst, dass jede einzelne Lösung durchsucht wird, um diese Knoten (oder eine Kombination von Sequenzen darin) zu untersuchen und zu erweitern. Daher verwendet ein BFS keinen heuristischen Algorithmus (oder einen Algorithmus, der in mehreren Szenarien nach einer Lösung sucht). Nachdem alle Knoten abgerufen wurden, werden sie zu einer Warteschlange hinzugefügt, die als First In, First Out-Warteschlange bezeichnet wird. Die Knoten, die noch nicht erforscht wurden, werden in einem Container mit der Bezeichnung 'open' gespeichert. Einmal erkundet, werden sie in einen Container mit der Bezeichnung "geschlossen" transportiert..

Depth First Search (auch bekannt als DFS) ist eine Suchmethode, die tiefer in einen untergeordneten Knoten einer Suche eingegraben ist, bis ein Ziel erreicht wird (oder bis es einen Knoten ohne andere Permutationen oder "Kinder" gibt). Nachdem ein Ziel gefunden wurde, springt die Suche zu einem vorherigen Knoten zurück, der eine Lösung erhalten hat, und wiederholt den Vorgang, bis alle Knoten erfolgreich durchsucht wurden. Daher werden Knoten weiterhin für weitere Erkundungen reserviert - dies wird als nicht rekursive Implementierung bezeichnet.

Die Merkmale des BFS sind räumliche und zeitliche Komplexität, Vollständigkeit, Vollständigkeitsnachweis und Optimalität. Die Raumkomplexität bezieht sich auf den Anteil der Anzahl von Knoten auf der tiefsten Ebene einer Suche. Zeitkomplexität bezieht sich auf die tatsächliche 'Zeit', die für die Betrachtung jedes Pfads verwendet wird, den ein Knoten bei einer Suche benötigt. Vollständigkeit ist im Wesentlichen eine Suche, bei der eine Lösung in einem Diagramm gefunden wird, unabhängig davon, um welche Art von Diagramm es sich handelt. Der Nachweis der Vollständigkeit ist die oberste Ebene, bei der ein Ziel in einem Knoten in einer bestimmten Tiefe gefunden wird. Die Optimalität bezieht sich schließlich auf ein BFS, das nicht gewichtet wird. Hierbei handelt es sich um ein Diagramm, das für die Kosten pro Einheit verwendet wird.

Eine DFS ist die natürlichste Ausgabe eines Spannbaums. Hierbei handelt es sich um einen Baum, der aus allen Scheitelpunkten und einigen Kanten in einem ungerichteten Diagramm besteht. In dieser Formation ist der Graph in drei Klassen unterteilt: Vorwärtskanten, die von einem Knoten auf einen Kindknoten zeigen; Hinterkanten, die von einem Knoten zu einem früheren Knoten zeigen; und Querkanten, die keines von diesen tun.

Zusammenfassung:

1. Ein BFS durchsucht jede einzelne Lösung in einem Diagramm, um seine Knoten zu erweitern. Eine DFS ist tief in einem Kindknoten vergraben, bis ein Ziel erreicht ist.

2. Die Merkmale eines BFS sind räumliche und zeitliche Komplexität, Vollständigkeit, Vollständigkeitsnachweis und Optimalität. Die natürlichste Ausgabe für ein DFS ist ein Spannbaum mit drei Klassen: Vorwärtskanten, Hinterkanten und Querkanten.