Explain BFS (Breadth First Search) vs DFS (Depth First Search) in cont

Explain BFS (Breadth First Search) vs DFS (Depth First Search) in context of graph traversal.

Answer»

Breadth-First Search (BFS) is a vertex-based method that begins at the root of the tree and traverses all nodes at the current depth level before moving on to nodes at the next depth level. It employs a Queue data structure that follows the first-in, first-out principle. In BFS, one vertex is visited and marked at a time, then its neighbours are visited and placed in the queue.
Depth First Search (DFS) is an edge-based approach. It employs the Stack data structure and operates in two stages: first, visited vertices are pushed into the stack, and subsequently, if no vertices are present, visited vertices are popped.

BFS	DFS
BFS STANDS for Breadth First Search.	DFS stands for Depth First Search.
BFS(Breadth First Search) employs the Queue data structure to determine the shortest path.	DFS(Depth First Search) employs the Stack data structure.
Because BFS reaches a vertex with the fewest number of EDGES from a source vertex, it can be used to identify a single source shortest path in an unweighted graph.	To get from a source vertex to a DESTINATION vertex in DFS, we may have to traverse through additional edges.
BFS is better at finding vertices that are CLOSE to the specified source.	When there are solutions that are not close to the source, DFS is a better option.
BFS has a time complexity of O(V + E) when using an Adjacency List and O(V^2) when using an Adjacency Matrix, where V stands for vertices and E stands for edges.	DFS also has a time complexity of O(V + E) when using an Adjacency List and O(V2) when using an Adjacency Matrix, where V stands for vertices and E stands for edges.
Here, the siblings of a node are visited before visiting the children.	Here, children of a node are visited before visiting the siblings.