Encyclopedia > Breadth first search

  Article Content

Breadth-first search

Redirected from 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
Bullying

... assumed power for any period of time without a legitimate basis of authority. The first to have the title of "Tyrant" was Pisistratus in 560 BC. In modern times ...

 
 
 
This page was created in 42.7 ms