Origin of the Breadth-First Search algorithm I'd like to know about the history of the breadth-first search algorithm. Can anyone point me to its inventor? It appears that the _depth_ -first search algorithm is attributed to a man named Charles Pierre Tremaux, but a google search for "inventor/history of breadth-first search" yields no fruit. Perhaps it was first formally laid out by someone who did a great deal of more important work in graph theory and algorithm design? (Turing? Dijkstra?)

The following remarks are found in the end chapter notes to Chapter 22, Elementary Graph Algorithms of Corman, et al., _Introduction to Algorithms_ , 2nd. ed., MIT Press, 2001, on page 560:

> _Breadth-first search was discovered by Moore [226] in the context of finding paths through mazes. Lee [198] independently discovered the same algorithm in the context of routing wires on circuit boards._

The relevant references are:

E. F. Moore (1959), The shortest path through a maze. In _Proceedings of the International Symposium on the Theory of Switching_ , Harvard University Press, pp. 285-292.

C. Y. Lee (1961), An algorithm for path connection and its applications. _IRE Transactions on Electronic Computers_ , EC-10(3), pp. 346-365.

* * *

Interestingly, the chapter notes give no such specific references for the depth-first search, noting only that it was well-known and widely used in the 1950s.