GoldenGolden
Breadth-first search

Breadth-first search

Breadth-first search is an algorithm for searching the nodes of a graph in order by their hop count from a starting node.

All edits

Edits on 10 Mar, 2021
Amy Tomlinson Gayle
Amy Tomlinson Gayle edited on 10 Mar, 2021
Edits made to:
Description (+37/-9 characters)
Topic thumbnail

Breadth-first search

AlgorithmBreadth-first search is an algorithm for searching the nodes of a graph in order by their hop count from a starting node.

Edits on 18 Dec, 2020
Carla Faraguna
Carla Faraguna edited on 18 Dec, 2020
Edits made to:
Article (+494/-494 characters)
Article

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. It uses the opposite strategy of depth-first search, which instead explores the node branch as far as possible before being forced to backtrack and expand other nodes.

Breadth-first search (BFSBFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. It uses the opposite strategy of depth-first search, which instead explores the node branch as far as possible before being forced to backtrack and expand other nodes.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. It was reinvented in 1959 by Edward F. Moore, who used it to find the shortest path out of a maze, and later developed by C. Y. Lee into a wire routing algorithm (published 1961).

Mevludin Mešanović
Mevludin Mešanović approved a suggestion from Golden's AI on 17 Dec, 2020
Edits made to:
Article (+11/-11 characters)
Article

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. It uses the opposite strategy of depth-first search, which instead explores the node branch as far as possible before being forced to backtrack and expand other nodes.BFS and its application in finding connected components of graphs were invented in 1945 by Konrad ZuseKonrad Zuse, in his (rejected) Ph.D. thesis on the Plankalkül programming language, but this was not published until 1972. It was reinvented in 1959 by Edward F. Moore, who used it to find the shortest path out of a maze, and later developed by C. Y. Lee into a wire routing algorithm (published 1961).

Mevludin Mešanović
Mevludin Mešanović approved a suggestion from Golden's AI on 17 Dec, 2020
Edits made to:
Article (+3/-3 characters)
Article

Breadth-first search (BFSBFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. It uses the opposite strategy of depth-first search, which instead explores the node branch as far as possible before being forced to backtrack and expand other nodes.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. It was reinvented in 1959 by Edward F. Moore, who used it to find the shortest path out of a maze, and later developed by C. Y. Lee into a wire routing algorithm (published 1961).

Matt McCarley
Matt McCarley edited on 17 Dec, 2020
Edits made to:
Timeline (+2 events) (+393 characters)
Article (+885 characters)
Article

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. It uses the opposite strategy of depth-first search, which instead explores the node branch as far as possible before being forced to backtrack and expand other nodes.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. It was reinvented in 1959 by Edward F. Moore, who used it to find the shortest path out of a maze, and later developed by C. Y. Lee into a wire routing algorithm (published 1961).

Timeline

1959

It was reinvented in 1959 by Edward F. Moore, who used it to find the shortest path out of a maze, and later developed by C. Y. Lee into a wire routing algorithm (published 1961).

1945

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.
Edits on 22 Apr, 2020
Golden AI"Attach Wikidata entity ID"
Golden AI edited on 22 Apr, 2020
Edits made to:
Infobox (+1 properties)
Infobox
Wikidata entity ID
Q325904
Edits on 1 Jan, 2017
Golden AI"Initial topic creation"
Golden AI created this topic on 1 Jan, 2017
Edits made to:
Description (+93 characters)
Article
Topic thumbnail

 Breadth-first search

Algorithm for searching the nodes of a graph in order by their hop count from a starting node

Golden logo
Text is available under the Creative Commons Attribution-ShareAlike 4.0; additional terms apply. By using this site, you agree to our Terms & Conditions.