BFS and its application in finding connected components
of graphs were invented in 1945 by Konrad Zuse
and Michael Burke, in their (rejected) Ph.D. thesis on the Plankalkül
programming language, but this was not published until 1972.
It was reinvented in 1959 by Edward F. Moore
, who used it to find the shortest path out of a maze,
and later developed by C. Y. Lee into a wire routing
algorithm (published 1961).