Breadth-first search
Algorithm exploring nodes level by level using a queue.
Breadth-first search (BFS) is an algorithm for searching tree or graph data structures, exploring all nodes at the present depth before moving to the next depth level. It is fundamental in computer science for tasks such as finding shortest paths and solving implicit infinite search spaces, and is guaranteed to find a solution node if one exists. The algorithm begins at a chosen root node and systematically examines every node at the current depth before proceeding to nodes at the next depth. To manage this process, BFS employs a queue data structure to store child nodes that have been encountered but not yet explored. In contrast to depth-first search, which may become trapped in an infinite branch when applied to implicit trees of potentially infinite size, BFS will always locate a solution node if one exists. However, BFS typically requires significantly more memory than depth-first approaches. The algorithm can be applied to both undirected and directed graphs from a given start node. In artificial intelligence state space search, revisiting vertices is often permitted, whereas theoretical algorithm analysis usually includes measures to prevent such repetitions. BFS was originally conceived by Konrad Zuse in 1945 within his rejected Ph.D. thesis on the Plankalkül programming language, though this work was not published until 1972. It was independently rediscovered in 1959 by Edward F. Moore, who applied it to finding the shortest path through a maze, and was later refined by C. Y. Lee into a wire routing algorithm published in 1961. The time complexity of BFS is expressed as O(V + E), where V represents vertices and E edges, as every vertex and edge may be explored in the worst case. When the graph size is known, the space complexity is O(V), in addition to the graph's own storage requirements. For graphs too large to store explicitly, BFS takes O(b^d) time and memory, where b is the average branching factor and d is the distance from the start node.
- field
- Computer science
- known_for
- Breadth-first search algorithm
- time_complexity
- O(|V| + |E|)
- space_complexity
- O(|V|)
Lore & Background
Breadth-first search (BFS) is an algorithm that systematically explores a tree or graph data structure by examining all nodes at the current depth level before moving to nodes at the next depth level. It begins at a designated root node and uses a queue—a first-in, first-out data structure—to store child nodes that have been encountered but not yet processed. The algorithm checks whether a vertex has been explored before adding it to the queue, preventing redundant work. BFS is complete for implicit, potentially infinite trees: if a solution node exists, the algorithm is guaranteed to find it, unlike plain depth-first search, which can become trapped in an infinite branch. However, BFS typically requires significantly more memory than depth-first approaches. The algorithm was originally conceived by Konrad Zuse in his 1945 Ph.D. thesis on the Plankalkül programming language, though this work was not published until 1972. It was independently reinvented by Edward F. Moore in 1959 for solving mazes by finding the shortest path, and later refined by C. Y. Lee into a wire routing algorithm. BFS can be applied to both undirected and directed graphs, and in artificial intelligence state-space search, repeated vertex visits are often permitted, whereas theoretical analyses typically include measures to prevent them. The algorithm’s time complexity is O(V + E) in the worst case, where V is the number of vertices and E is the number of edges; its space complexity is O(V), excluding the graph’s storage. For very large or infinite graphs, BFS requires O(b^d) time and memory, where b is the average branching factor and d is the distance from the start node.
Reader's Guide
Breadth-first search is a cornerstone algorithm in computer science, particularly for graph traversal and shortest path problems. Its significance lies in its completeness: when applied to infinite implicit graphs, BFS is guaranteed to find a goal state if one exists, unlike depth-first search which may get lost in infinite branches. The algorithm's time complexity is O(|V| + |E|), exploring every vertex and edge in the worst case, while space complexity is O(|V|) when additional data structures track visited vertices. BFS is widely used in artificial intelligence for state space search, in chess engines to find winning positions, and in network routing algorithms. Its non-recursive implementation differs from depth-first search primarily by using a queue instead of a stack and by checking exploration status before enqueueing. The algorithm produces a breadth-first tree and parent links that trace the shortest path back to the root. BFS ordering of vertices is a possible output of the algorithm's application to a graph.
Did You Know?
- BFS uses a queue (First In First Out) while depth-first search uses a stack (Last In First Out).
- BFS is complete for infinite implicit graphs, guaranteeing to find a goal state if one exists.
Frequently Asked Questions
What are Breadth-first search's powers and role?
BFS explores nodes level by level using a queue, making it the canonical method for finding shortest paths in unweighted graphs. It also handles implicit or even infinite search spaces, guaranteeing a solution is found whenever one exists.
How does Breadth-first search's story end?
The algorithm terminates once it locates the target node or has exhausted every reachable vertex in the graph. Its total work is bounded by O(|V| + |E|), since each vertex and edge is processed at most once.
Why is Breadth-first search important to the canon?
BFS is a foundational building block of computer science, underpinning pathfinding, connectivity checks, and many higher-level algorithms. Its completeness guarantee—finding a solution if one exists—gives it a special status among search strategies.
What is Breadth-first search's known weakness?
Because it must keep every discovered-but-unprocessed node in the queue, its space usage scales to O(|V|), which can become prohibitive on very large or wide graphs. This memory overhead is the main trade-off compared to depth-first alternatives.
More in Algorithms And Data Structures 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record