5
$\begingroup$

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?)

$\endgroup$
2
  • $\begingroup$ Pretty sure the first BFS algorithm was neanderthals zigzagging to find animal trails. $\endgroup$
    – DanielV
    Commented Jan 17, 2014 at 23:05
  • $\begingroup$ @DanielV Doubtful. $\endgroup$
    – JeremyKun
    Commented Jan 18, 2014 at 2:23

1 Answer 1

Reset to default
9
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .