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
Time Complexity
Time Complexity (category) Credited ToKonrad Zuse (1945), reinvented by Edward F. Moore (1959) 2 Connections
Credited To
Source Wikipedia, Breadth-first search
In Field
Invented By
Source Wikipedia, Breadth-first search
Sources
1. Breadth-First Search (Wikipedia)
Wikipedia infobox: time complexity linearQuote, Wikipedia infobox: time complexity linear
linear
2. Wikipedia, Breadth-first search
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.
Invented By: Konrad Zuse, History section
BFS and its application in finding connected components of graphs were invented in 1945 by Konrad Zuse
Credited To: Konrad Zuse, History section
BFS and its application in finding connected components of graphs were invented in 1945 by Konrad Zuse
View the SourceWikidata: Breadth-First Search
Wikidata Q325904, class allow-list match (w-wdresolver-0926)View the Source 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.