Invention of breadth-first search

Breadth-first search is an algorithm for exploring a graph or tree, which starts at one node and visits all its neighbours before moving on to the nodes at the next level. It uses a queue to keep track of the nodes still to be explored, and in a graph with unweighted edges it finds the shortest path, in terms of number of edges, from the starting node to every other reachable node. The method was described by the German engineer Konrad Zuse in the 1940s in a work that was not published until later, and it was independently rediscovered by others, including Edward F. Moore, who used it to find the shortest path out of a maze. It is a basic technique in computing, used in network routing, social network analysis and web crawling.

Open on the timeline