Overview
Breadth-First Search uses a queue to expand the current frontier before moving to the next level. In an unweighted graph, this gives shortest-path distances by edge count.
FoundationSource checked
Breadth-First Search
Explores a graph from a start node in increasing number of edges.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Beginner
- Family
- Graph Traversal
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 25
- Code example
- Ready
- Visualization
- Ready
- Aliases
- BFS
Core Concepts
queue frontierlevel-order traversalvisited setunweighted distance
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)
When to Use
- Use it for shortest paths when every edge has the same cost.
- Use it when you need nodes grouped by distance from a start node.
- Use it for connected-component or reachability checks.
When Not to Use
- Avoid it for weighted shortest paths unless all weights are equal.
- Avoid it when the frontier would be too large to store.
- Avoid it when depth-first memory behavior is a better fit.
What It Does
- Visits nodes by distance from the start
- Tracks discovered nodes to avoid repeated work
Use Cases
- Shortest paths in unweighted graphs
- Level-order tree traversal
- Reachability in networks
Inputs
- Graph
- Starting node
Outputs
- Traversal order
- Reachability information
- Unweighted shortest path tree
Pseudocode
- 1.Put the start node in a queue
- 2.Mark the start node as visited
- 3.Remove the next node from the queue
- 4.Add each unvisited neighbor to the queue
- 5.Repeat until the queue is empty
Canonical Example
- Input
- graph = {A: [B, C], B: [D], C: [], D: []}, start = A
- Output
- visited = [A, B, C, D]
- Explanation
- A is visited first, then its neighbors B and C, then D from the next level.
Implementation Notes
- Mark a node as discovered when it is enqueued.
- Store parent pointers if a shortest path, not just distance, is needed.
- Keep traversal state separate from the graph representation.
Common Pitfalls
- Marking nodes only when dequeued, which can enqueue the same node many times.
- Treating BFS distances as weighted shortest paths.
- Leaving edge direction ambiguous in directed graphs.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow rings of nodes expanding outward from the start.
Step 1 of 5: Put the start node in a queue
graph-levelsNotes
BFS gives shortest paths by number of edges only in unweighted graphs.
Sources (1)
What each reference supports for this entry.
CLRS
BookTextbook reference for the algorithmic family and analysis of Breadth-First Search.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Has variantsLee Algorithm
Pathfinding · Core
Lee routing is a grid-based breadth-first search for shortest paths in unweighted grids.
Compare with thisUsesDeque
Data Structures · Foundation
A deque or queue supports breadth-first frontier order.
Compare with thisUsed byFlood Fill
Image Processing · Foundation
Flood fill often uses BFS-style frontier expansion over grid cells.
Compare with thisUsesGraph Adjacency List
Data Structures · Foundation
BFS commonly iterates outgoing neighbors from adjacency lists.
Compare with thisRelationships
View full relationship pagePrerequisite ofBidirectional Search
Bidirectional search often runs BFS-style expansions from both ends.
Prerequisite ofDijkstra's Algorithm
Dijkstra's Algorithm extends frontier expansion to weighted graphs.
Related Algorithms
Tags
GraphTraversalQueueClassic