A graph traversal algorithm that explores a graph outward from a starting vertex one whole layer of neighbors at a time, using a queue to guarantee that the shortest path in an unweighted graph is found first.
Facts
Credited ToKonrad Zuse (1945), reinvented by Edward F. Moore (1959) 1 Connections
Sources
1. Wikipedia, Breadth-first search
Lead sectionQuote, Lead section
BFS and its application in finding connected components of graphs were invented in 1945 by Konrad Zuse, in his (rejected) Ph.D. thesis on the Plankalkül programming language, but this was not published until 1972.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.