Breadth first search traverses the graph starting from the source node in a expanding fashion. After visiting each node, it visits the nodes adjacent to the visited node.
Because of this, we can also keep track of the distance each vertex is from the source node (using the
As compared to DFS which uses recursion to traverse, BFS is implemented in an iterative fashion with the help of a queue data structure.
The time complexity for BFS is same as DFS,
O(|V| + |E|), which is linear.
Explanation is same as for DFS.
- If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better.
- If the tree is very deep and solutions are rare, depth first search (DFS) might take an extremely long time, but BFS could be faster.
- If the tree is very wide, a BFS might need too much memory, so it might be completely impractical.
- If solutions are frequent but located deep in the tree, BFS could be impractical.
- If the search tree is very deep you will need to restrict the search depth for depth first search (DFS), anyway (for example with iterative deepening).