Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 at 23:05
    
@DanielV Doubtful. –  JeremyKun Jan 18 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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.