Editing Breadth-first search (section)

{{Short description|Algorithm to search the nodes of a graph}}
{{more citations needed|date=April 2012}}
[[Image:Animated BFS.gif|thumb|187px|Animated example of a breadth-first search. Black: explored, grey: queued to be explored later on]]
[[File:BFS-Algorithm Search Way.gif|thumb|BFS on [[Maze-solving algorithm]]]]
[[File:Tic-tac-toe-game-tree.svg|thumb|187px|Top part of [[Tic-tac-toe]] game tree]]
'''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 win 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>

Breadth-first search can be generalized to both [[undirected graph]]s and [[directed graph]]s with a given start node (sometimes referred to as a 'search key').<ref>{{cite web |url=http://www.graph500.org/specifications#sec-5 |title=Graph500 benchmark specification (supercomputer performance evaluation) |publisher=Graph500.org, 2010 |access-date=2015-03-15 |archive-url=https://web.archive.org/web/20150326055019/http://www.graph500.org/specifications#sec-5#sec-5 |archive-date=2015-03-26 |url-status=dead }}</ref> In [[state space search]] in [[artificial intelligence]], repeated searches of vertices are often allowed, while in theoretical analysis of algorithms based on breadth-first search, precautions are typically taken to prevent repetitions.

BFS and its application in finding [[Connected component (graph theory)|connected components]] of graphs were invented in 1945 by [[Konrad Zuse]], in his (rejected) Ph.D. thesis on the [[Plankalkül]] programming language, but this was not published until 1972.<ref name=":0">{{citation|title=Der Plankalkül|first=Konrad|last=Zuse|author-link=Konrad Zuse|publisher=Konrad Zuse Internet Archive|year=1972|url=http://zuse.zib.de/item/gHI1cNsUuQweHB6|language=de}}. See pp. 96–105 of the linked pdf file (internal numbering 2.47–2.56).</ref> It was reinvented in 1959 by [[Edward F. Moore]], who used it to find the shortest path out of a maze,<ref>{{cite conference|first=Edward F.|last=Moore|author-link=Edward F. Moore|year=1959|contribution=The shortest path through a maze|title=Proceedings of the International Symposium on the Theory of Switching|publisher=Harvard University Press|pages=285–292}} As cited by Cormen, Leiserson, Rivest, and Stein.</ref><ref name="skiena">{{cite book |first=Steven |last=Skiena |author-link=Steven Skiena |title=The Algorithm Design Manual |publisher=Springer |year=2008 |page=480 |doi=10.1007/978-1-84800-070-4_4|chapter=Sorting and Searching |isbn=978-1-84800-069-8 |bibcode=2008adm..book.....S }}</ref> and later developed by C. Y. Lee into a [[Routing (electronic design automation)|wire routing]] algorithm (published in 1961).<ref>{{cite journal |title=An Algorithm for Path Connections and Its Applications |first1=C. Y. |last1=Lee |journal=IRE Transactions on Electronic Computers |year=1961 |issue=3 |pages=346–365 |doi=10.1109/TEC.1961.5219222 |s2cid=40700386 }}</ref>