Breadth-first search (BFS)
Búsqueda en anchura (BFS)
- Date
- 1945 (Zuse, inédito) / 1959 (Moore) · confidence medium
- Place
- Bell Labs, Murray Hill, New Jersey, United States
- Credited to
- Edward F. Moore (with an earlier, unpublished, independent formulation by Konrad Zuse in 1945)
- Field
- Knowledge & symbols
What was discovered
Moore published the breadth-first search algorithm to find the shortest path out of a maze, exploring a graph level by level from the starting node. Konrad Zuse had conceived the same idea in 1945 for connected components of graphs, but his work remained unpublished until 1972.
Konrad Zuse devised the same algorithm in 1945 within his thesis on the Plankalkül language, but it was not published until 1972, so the scientific community credits the public reinvention to Moore.
What it led to
- Circuit routing algorithms (C. Y. Lee, 1961)
- Algorithmic graph theory
Built on
- Euler's graph theory