Home

About 

Breadth-First Search (BFS) is a type of uninformed (blind) search algorithms.

BFS traverses search trees horizontally first, looking for a goal.

Works on a FIFO (first-in, first-out) principle of a queue.

Start (initial node) is added to a queue.

Initial node is popped from the queue, and checked if it's a goal; if not, BFS expands it, and appends its children to the queue (at the end).

Then repeats the same for each node in a queue recursevily, in order of their insertion to the queue (FIFO).

Pops node from the queue, checks if it's a goal; appends its children to the end of a queue.

Thus, BFS algorithm always checks all nodes in the same depth level first, before going deeper.

Algorithm's Metrics:

Completeness: complete - it will eventually explore all possible states; if a goal exists, it will find it

Optimality: optimal - if cost of each action is uniform and equal

b - branching factor; d - depth

Time Complexity: O(b^d)

Space Complexity: O(b^d) [stores all nodes at a level → can explode quickly]