1. Breadth First Search:

• • Breadth First Search (BFS) is the most common searching algorithm to traverse a tree or graph.
• • This algorithm searches the result in a breadth wise manner i.e., it starts traverse from the root node and then traverse towards the successor nodes level wise that means after root node it traverses all the successor in the current level before moving to the next level.
• • Breadth First search algorithms are the general graph search algorithm.
• • It implemented using the First in First Out (FIFO) Queue Data Structure.

Advantages

• • Breadth First Search (BFS) will provide the solution if any solution exists.
• • If there are more than one solution for a given problem then it will find the minimal solution, which requires the least number of steps.

Disadvantages

• • Breadth First Search (BFS) requires a lot of memory since it stores each level of the tree in to the memory to expand the next level.
• • If the solution is too far from the root node, then it takes too much time to find the solution for a given problem.

Time Complexity

Time complexity of BFS algorithm can be obtained by the number of nodes traversed in BFS until the Shallowest node. Where d is the depth of Shallowest node and b is a node at every state.
T(b)=1+b²+b³+....+b^d=O(b^d)

Space Complexity

Space complexity of Breadth First Search (BFS) is given by the memory size of frontier which is O(b d ).

Completeness

Breadth First Search (BFS) is complete that mean if the solution of a given problem is exists at any node with a finite depth, then the algorithm definitely finds a solution.

Optimality

Breadth First Search (BFS) is Optimal if path coast is a non-decreasing function of the depth of the node.

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc