GeeksforGeeks

Breadth First Search

BFS steht für Breadth First Search und ist ein vertexbasiertes Verfahren, um einen kürzesten Pfad in einem Graphen zu finden. Sie verwendet eine Warteschlangen-Datenstruktur, die dem Prinzip „first in first out“ folgt. Bei BFS wird jeweils ein Knoten ausgewählt, wenn er besucht und markiert wird, dann werden seine benachbarten Knoten besucht und in der Warteschlange gespeichert. Es ist langsamer als DFS.
Ex-

 A / \ B C / / \ D E F

Ausgabe ist:

A, B, C, D, E, F

Depth First Search

DFS steht für Depth First Search und ist eine kantenbasierte Technik. Es verwendet die Stack Datenstruktur, führt zwei Stufen durch, zuerst werden besuchte Scheitelpunkte in den Stack geschoben und zweitens, wenn es keine Scheitelpunkte gibt, werden besuchte Scheitelpunkte gepoppt.
Ex-

 A / \ B C / / \ D E F

Output ist:

A, B, D, C, E, F

BFS vs DFS

BFS(Breadth First Search) verwendet eine Queue-Datenstruktur, um den kürzesten Pfad zu finden.

S.NO	BFS	DFS
	BFS steht für Breadth First Search.	DFS steht für Depth First Search.
	DFS(Depth First Search) verwendet die Datenstruktur Stack.
	BFS kann verwendet werden, um den kürzesten Weg in einem ungewichteten Graphen zu finden, da bei BFS ein Vertex mit einer minimalen Anzahl von Kanten von einem Quellvertex aus erreicht wird.	In DFS müssen wir möglicherweise mehr Kanten durchqueren, um einen Zielknoten von einer Quelle aus zu erreichen.
	BFS ist besser geeignet, um Knoten zu suchen, die näher an der gegebenen Quelle liegen.	DFS ist besser geeignet, wenn es Lösungen gibt, die von der Quelle entfernt sind.
	BFS berücksichtigt zuerst alle Nachbarn und eignet sich daher nicht für Entscheidungsbäume, die in Spielen oder Puzzles verwendet werden.	DFS ist besser geeignet für Spiel- oder Rätselprobleme. Wir treffen eine Entscheidung und untersuchen dann alle Pfade durch diese Entscheidung. Und wenn diese Entscheidung zu einer Gewinnsituation führt, hören wir auf.
	Die Zeitkomplexität von BFS ist O(V + E), wenn eine Adjazenzliste verwendet wird, und O(V^2), wenn eine Adjazenzmatrix verwendet wird, wobei V für Scheitelpunkte und E für Kanten steht.	Die Zeitkomplexität von DFS ist ebenfalls O(V + E), wenn Adjacency List verwendet wird, und O(V^2), wenn Adjacency Matrix verwendet wird, wobei V für Vertices und E für Edges steht.

Bitte lesen Sie auch BFS vs DFS für Binary Tree für die Unterschiede für ein Binary Tree Traversal.