Write down the advantages and disadvantages of BFS and DFS traversal algorithm.
Subject Algorithm Design
NU Year Set: 4.(a) Marks: 5 Year: 2008

ADVANTAGES OF BREADTH-FIRST SEARCH

  1. Breadth-first

    search will never get trapped exploring the useless path forever.

  2. If there is a solution, BFS will definitely find it out.

  3. If there is more than one solution then BFS can find the minimal one that requires less number of steps.

DISADVANTAGES OF BREADTH-FIRST SEARCH 

  1. The main drawback of Breadth-first search is its memory requirement. Since each level of the tree 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). As a result, BFS is severely space-bound in practice so will exhaust the memory available on typical computers in a matter of minutes.

  2. If the solution is farther away from the root,

    breadth-first

    search will consume a lot of time.

 

Advantages of Depth First Search:

  1. Consumes less memory

  2. Finds the larger distant element(from source vertex) in less time.

Disadvantages of BFS:

  1. May not find

    optimal

    solution to the problem.

  2. May get trapped in searching useless path.

Login to post your comment.