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.
- field
- Computer science
- known_for
- Breadth-first search algorithm
- time_complexity
- O(|V| + |E|)
- space_complexity
- O(|V|)
Lore & Background
Moore, who used it to find the shortest path out of a maze, and later developed by C. Y. The algorithm uses a queue (First In First Out) to keep track of child nodes encountered but not yet explored, and it checks whether a vertex has been explored before enqueueing it.
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
Elsewhere in the Algorithms And Data Structures universe
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