Breadth-first search: Difference between revisions

Revision as of 06:42, 2 July 2025

Revision as of 03:17, 20 July 2025

Line 6:

'''Breadth-first search''' ('''BFS''') is an [[algorithm]] for searching a [[Tree (data structure)|tree]] data structure for a node that satisfies a given property. It starts at the [[tree (data structure)#Terminology|tree root]] and explores all nodes at the present [[tree (data structure)#Terminology|depth]] prior to moving on to the nodes at the next depth level. Extra memory, usually a [[queue (data structure)|queue]], is needed to keep track of the child nodes that were encountered but not yet explored.

For example, in a [[chess endgame]], a [[chess engine]] may build the [[game tree]] from the current position by applying all possible moves and use breadth-first search to find a winwinning position for White. Implicit trees (such as game trees or other problem-solving trees) may be of infinite size; breadth-first search is guaranteed to find a solution node<ref>that is, a node satisfying the specified property</ref> if one exists.

In contrast, (plain) [[depth-first search]] (DFS), which explores the node branch as far as possible before backtracking and expanding other nodes,<ref>{{cite book |author=Cormen Thomas H. |display-authors=etal |title=Introduction to Algorithms |publisher=MIT Press |date=2009 |chapter=22.3}}</ref> may get lost in an infinite branch and never make it to the solution node. [[Iterative deepening depth-first search]] avoids the latter drawback at the price of exploring the tree's top parts over and over again. On the other hand, both depth-first algorithms typically require far less extra memory than breadth-first search.<ref>{{Cite journal |last=Korf |first=Richard E. |author-link=Richard E. Korf|date=1985 |title=Depth-First Iterative Deepening: An Optimal Admissible Tree Search |url=https://doi.org/10.7916/D8HQ46X1 |journal=Artificial Intelligence |language=en |issue=27 |pages=99–100 |doi=10.7916/D8HQ46X1}}</ref>