Breadth-first search

Breadth-first search (BFS) is a tree search algorithm used for traversing or searching a tree (graph theory) or tree structure. Intuitively, you start at the root node and explore all the neighboring nodes. Then for each of those nearest nodes, explore their unexplored neighbor nodes, and so on until it finds the goal.

Formally, BFS is an uninformed search method that aims to expand and examine all nodes of a tree systematically in search of a solution. In other words, it exhaustively searches the entire tree without considering the goal until it finds it. It does not use a heuristic.

From the standpoint of the algorithm, all nodes obtained by expanding any node are placed at the end of the search queue. In typical implementations, nodes that have not yet been examined for their neighbors are placed in some container (such as a queue or linked list) called "open" and then once examined are placed in the container "closed".

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 smallest number of steps to reach the goal.
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.

When searching in a cyclic graph (one that is not a tree) for a shortest path, BFS may be adapted by keeping a bit on each node to indicate that it has already been visited. However, other algorithms such as Dijkstra's algorithm solve the same task more efficiently.

External links

Dictionary of Algorithms and Data Structures: breadth-first search