BFS (Breadth-First Search)
Breadth-first search (BFS) traverses a graph or tree level by level: visit every vertex one step from the source, then two steps, and so on — using a queue to keep the order.
Because it goes layer by layer, BFS gives the shortest path on an unweighted graph. You need a "visited" set to avoid looping forever when there are cycles; worst-case memory is proportional to the width of one level.
Like an army advancing in waves — finish one wave before the next begins.
- It traverses level by level and guarantees the shortest path on an unweighted graph.
- Think of a message spreading: every person who receives it passes it to their neighbors before those neighbors pass it on.
How to spot it
When you see these cues in the problem, reach for BFS (Breadth-First Search)
| Keyword in the problem | Why it points to this topic |
|---|---|
| shortest path | BFS works on unweighted graphs |
| level-order traversal | Sweep tree or graph one level at a time |
| flood fill from a source | Connected regions and flood-fill problems |
| minimum number of steps | BFS naturally counts minimum steps |
When to use
3 typical situations where this topic applies
You need the shortest path on an unweighted graph
You need to traverse a tree or graph level by level (level-order)
"Spreading out" problems from a source: minimum distance, fewest steps
When NOT to use
3 situations where this topic doesn't fit — know them so you don't overuse them
The graph has edges with different weights and you need the shortest path: use Dijkstra / Bellman-Ford
You need to explore deep first (find any path, backtracking): DFS fits better
The graph is so wide that the queue uses a lot of memory: consider iterative deepening DFS
Illustration
Press Play to see each step.
- Current
- In queue
- Visited
// Iterative BFS — traverse level by levelconst queue = [start], visited = new Set()while (queue.length) { const node = queue.shift() visited.add(node) for (const nb of adj[node]) { if (!visited.has(nb)) queue.push(nb) }}Code template
Most problems in this topic share this scaffold — copy it, then fill in the problem-specific logic.
function bfs(start: Node, graph: Graph): R {
const queue: Node[] = [start]
const visited = new Set<Node>([start])
while (queue.length > 0) {
const node = queue.shift()!
// Process the node
visit(node)
// Enqueue unvisited neighbours
for (const next of graph.neighbors(node)) {
if (!visited.has(next)) {
visited.add(next)
queue.push(next)
}
}
}
}Recap
A quick summary — reread it before your interview
Key points
Use a queue (FIFO) — as opposed to DFS, which uses a stack
Mark visited BEFORE pushing onto the queue to avoid duplicates (not when you pop)
BFS guarantees level order → the path to each node is the shortest on an unweighted graph
Count levels by processing one whole "layer" of the queue per round (save queue.length before iterating)
Common mistakes
Marking visited on pop instead of on push → a node can enter the queue multiple times, causing duplicates
Confusing BFS with DFS: BFS uses a queue, DFS uses a stack or recursion
Forgetting to handle graphs with cycles (you need a visited set)
Complexity
Time O(V + E), Space O(V) — V là số đỉnh, E là số cạnhPractice problems for this topic
Grouped by difficulty — work through them in order to build confidence