Home > Breadth-first search

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".

When searching in an unweighted 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.

• 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 space complexity linear in the size(edges plus vertices) of the tree/graph searched as it needs to store all expanded nodes in memory.
• BFS has time complexity linear in the size(edges plus vertices) of the graph or tree searched.

For the following graph:

a breadth-first search starting at A, and assuming that the left edges in the shown graph are chosen before right edges, will result in the search visiting the nodes in the following order: A, B, C, E, D, F, G. Compare with depth-first search.

1 pseudocode

2 See also

• depth-first search
• Iterative deepening depth-first search
• best-first search

• BFS is also the SCO UNIXWare Boot File System
• BFS is also the BeOSBeOS is a personal computer operating system developed by Be Incorporated in 1990 as a media OS. A highly modular OS written in completely new code (and not based on UNIX, a common misconception due to Be's inclusion of the Bash command shell and some sim Be File SystemThe Be File System (BFS, BeFS) is the native file system for the BeOS operating system. BFS was developed by Dominic Giampaolo and Cyril Meurillon in 1996 over a ten month period to provide BeOS with a modern 64-bit capable journaling file system. It is c

3 External links

• Dictionary of Algorithms and Data Structures: breadth-first search
• C++ Boost Graph Library: Breadth-First Search

BFS can also stand for the pop punkPop punk is really used for two separate subgenres of punk rock music: the kind typically found on Lookout! Records, which stray very little from the three-chord formula that The Ramones pioneered, as well as a newer subgenre of melodic, more emotional pu band, Bowling for SoupBowling for Soup is a Wichita Falls-based punk-pop band formed in 1994, best known for their singles "Girl All The Bad Guys Want" in 2002 on Drunk Enough to Dance and "1985" in 2004 on Hangover You Don't Deserve''. The band's name is derived from comedian.