Encyclopedia > Breadth-first search

  Article Content

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:

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Lake Ronkonkoma, New York

... total population of 19,701. Geography Lake Ronkonkoma is located at 40°49'47" North, 73°6'47" West (40.829709, -73.113015)1. According to the United Stat ...

This page was created in 37.8 ms