Take the 2-minute tour ×

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

share|improve this question
Pretty sure the first BFS algorithm was neanderthals zigzagging to find animal trails. –  DanielV Jan 17 '14 at 23:05
@DanielV Doubtful. –  JeremyKun Jan 18 '14 at 2:23

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer

Your Answer


