Breadth first search (BFS) algorithm also starts at the root of the Tree (or some arbitrary node of a graph), but unlike DFS it explores the neighbor nodes first, before moving to the next level neighbors. In other words, BFS explores vertices in the order of their distance from the source vertex, where distance is the minimum length of a path from source vertex to the node.
Below graph shows order in which the nodes are discovered in DFS.
Below graph shows order in which the nodes are discovered in BFS.
Finding nodes in any connected component of a graph
Ford–Fulkerson method for computing the maximum flow in a flow network
Serialization/Deserialization of a binary tree
4. DFS and BFS for Trees
Trees may be traversed in multiple ways in depth-first order or breadth-first order. Depth-first search for trees can be implemented using pre-order, in-order, and post-order while breadth-first search for trees can be implemented using level order traversal.
In BFS, we need to maintain a separate data structure for tracking the tree/graph nodes yet to be visited. This is easily done iteratively using Queue data structure.
In contrast to BFS, DFS don’t need any additional data structure to store the tree/graph nodes. The recursive implementation of DFS uses the recursive call stack.
6. Time Complexity
The time complexity of both DFS and BFS traversal is O(N + M) where N is number of vertices and M is number of edges in the graph.
Please note that M may vary between O(1) and O(N2), depending on how dense the graph is.
7. Memory Requirements
The memory taken by DFS/BFS heavily depends on the structure of our tree/graph. The maximum memory taken by DFS (i.e. by recursion call stack) is equal to the depth of the tree and the maximum memory taken by BFS is equal to the width of the tree.
8. When to use DFS and BFS?
If we know the solution lies somewhere deep in a tree or far from the source vertex in graph, use DFS. If we know the solution is not that far from the source vertex, use BFS.
If our tree is very wide, use DFS as BFS will take too much memory. Similarly if our tree is very deep, choose BSF over DFS.