Breadth-first search

Breadth First Search (BFS) is a way of traversing or searching a Tree (graph theory) or Tree structure. Intuitively, you start at the root and explore all the neighboring nodes (only!) first. Then for each of those nearest nodes, explore their unexplored neighbor nodes, and so on.

Formally, BFS is an uninformed search method that aims to expand and examine all nodes of a tree systematically in search of a solution.

From the stand-point of the algorithm, all nodes obtained by expanding any node are placed at the end of the search Queue.

• BFS is complete - it finds a goal-state if one exists. (That is, it reaches every node on the tree).
• BFS is optimal - it finds the lowest cost path to the goal, if the cost of any one step in the path is never negative.
• BFS has high space complexity - as it needs to store all expanded nodes in memory.
• BFS also has high time complexity, as the number of nodes to be examined grows exponentially.

---

See also:

• depth-first search
• best-first search