Breadth-First Search is an uninformed search algorithm that systematically explores a graph or search tree in increasing order of depth. It begins by placing the initial node in a queue. The algorithm removes the front node, checks whether it satisfies the goal condition, and adds its unvisited successors to the back of the queue. The process continues until a goal is found or no nodes remain. A first-in, first-out queue ensures that nodes at a smaller depth are processed before nodes at a greater depth. BFS is complete when the branching factor is finite and a goal exists at a finite depth. It finds a minimum-number-of-edges path in an unweighted graph, or when every action has the same cost. It is not generally optimal when action costs differ. BFS can require substantial memory because it stores many frontier nodes. With branching factor b and shallowest goal depth d, its typical time and space complexity are O(b^(d+1)).
Breadth-First Search
Breadth-First Search (BFS) explores a graph level by level, visiting the shallowest unexpanded nodes before deeper nodes.
Time Complexity: O(b^(d+1)); Space Complexity: O(b^(d+1))
Explanation
Variables
| Symbol | Meaning |
|---|---|
b | The branching factor, or number of successors per node in the complexity model. |
d | The depth of the shallowest goal node. |
Queue | A first-in, first-out data structure used to store the frontier. |
Visited Set | A collection of states already discovered or explored. |
Example or application
Consider a graph where A connects to B and C, B connects to D and E, and C connects to F. Starting from A, BFS visits A first, then B and C, and then D, E, and F. The order within the same level depends on the order in which neighbors are added.
Text
BFS uses a first-in, first-out queue. It starts from an initial node, visits its neighbors, and then explores the neighbors of those nodes. In an unweighted graph, it finds a path with the fewest edges.
Key Points
BFS explores nodes level by level.
It uses a FIFO queue.
It is complete under standard finite-branching assumptions when a finite-depth goal exists.
It finds a shortest path by number of edges in an unweighted graph.
It can consume considerable memory.
Applications
Shortest-path search in unweighted graphs
Social-network connection analysis
Web crawling
Network broadcasting
Level-order traversal of trees
Learning Outcomes
Explain how BFS explores a graph.
Describe the role of a FIFO queue.
Identify the conditions under which BFS is complete and optimal.
Practice Questions
Which data structure does BFS use?
Why does BFS find a shortest path in an unweighted graph?
What are the typical time and space complexities of BFS?
Related Concepts
Uninformed Search Strategies
Depth-First Search
Queue Data Structure
Shortest-Path Algorithms
Common Mistakes
Using a stack instead of a queue when implementing standard BFS.
Assuming BFS finds the lowest-cost path when edge weights differ.
Failing to track visited nodes in a cyclic graph.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Cormen, T. H. et al. Introduction to Algorithms, section on Breadth-First Search.
- Russell, S. and Norvig, P. Artificial Intelligence: A Modern Approach, uninformed search.
Suggest a correction or source · More in Artificial Intelligence & Machine Learning