Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’), and explores all of the neighbour nodes at the present depth prior to moving on to the nodes at the next depth level.

It is an uninformed searching algorithm.

An uninformed searching algorithm has no additional information on the goal node other than the one provided in the problem definition. The plans to reach the goal state from the start state differ only by the order and/or length of actions. Uninformed search is also called Blind search.

• Space complexity: Equivalent to how large can the fringe get. S(n) = O(n^s) where n is branching factor and s is the depth of search.

• Completeness: BFS is complete, meaning for a given search tree, BFS will come up with a solution if it exists.

• Optimality: BFS is optimal as long as the costs of all edges are equal.

Code file: src/BFS.js