Disadvantages of Breadth First Search

Applications of Breadth First Search:

1. Shortest Path and Minimum Spanning Tree for unweighted graph: In an unweighted graph, the shortest path is the path with the least number of edges. With Breadth First, we always reach a vertex from a given source using the minimum number of edges. Also, in the case of unweighted graphs, any spanning tree is Minimum Spanning Tree and we can use either Depth or Breadth first traversal for finding a spanning tree....

Advantages of Breadth First Search:

BFS will never get trapped exploring the useful path forever. If there is a solution, BFS will definitely find it. If there is more than one solution then BFS can find the minimal one that requires less number of steps. Low storage requirement – linear with depth. Easily programmable....

Disadvantages of Breadth First Search:

The main drawback of BFS is its memory requirement. Since each level of the graph must be saved in order to generate the next level and the amount of memory is proportional to the number of nodes stored the space complexity of BFS is O(bd ), where b is the branching factor(the number of children at each node, the outdegree) and d is the depth. As a result, BFS is severely space-bound in practice so will exhaust the memory available on typical computers in a matter of minutes....