Breadth-first search
|
|
In computer science, breadth-first search (BFS) is a tree search algorithm used for traversing or searching a tree, tree structure, or graph. 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 child nodes obtained by expanding a node are added to a FIFO 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 so long as the tree it is searching has a finite number of branches - it finds a goal-state if one exists. (That is, it reaches every node on the tree.)
- BFS is optimal if step costs are identical - BFS will find the shallowest solution in a search tree, not necessarily the best one. In the case of non-uniform step costs, the shallowest solution is not necessarily the best one.
- 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.
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.
| Contents |
Pseudocode
function breadthFirstSearch (Start, Goal) {
enqueue(Queue,Start)
while notEmpty(Queue)) {
Node := dequeue(Queue)
if Node = Goal {
return Node
}
for each Child in Expand(Node) {
if notVisited(Child) {
setVisited(Child)
enqueue(Queue, Child)
}
}
}
}
Uses and extensions
BFS can be used to identify connected components as well as for testing bipartiteness of graphs. The set of nodes reached by a BFS are the largest connected component containing the start node. If there are no edges joining nodes in the same BFS layer, then the graph must contain an odd length cycle and be non-bipartite.
See also
External links
- Dictionary of Algorithms and Data Structures: breadth-first search (http://www.nist.gov/dads/HTML/breadthfirst.html)
- C++ Boost Graph Library: Breadth-First Search (http://www.boost.org/libs/graph/doc/breadth_first_search.html)de:Breitensuche