BFS Visualization: Breadth-First Search Simulator

Q: What is the time complexity of BFS?

O(b^d) time and space, where b is the branching factor and d the depth of the shallowest goal. On a graph it is O(V + E).

About this visualization

Breadth-first search explores a graph level by level using a first-in-first-out queue, so it always finds the path with the fewest edges. Draw your own graph, choose the start and goal, and watch the frontier queue and expansion order change step by step.

How it works

Put the start node in a FIFO queue.
Take the node at the front; if it is the goal, stop. Otherwise add its unseen neighbours to the back of the queue.
Because the queue is first-in first-out, the search spreads outward one level at a time.

Formulas used

Time and space: $O(b^{d})$
$b$ = branching factor, $d$ = depth of the shallowest goal

Worked example

On the Romania road map from Arad to Bucharest, BFS expands Arad, then Sibiu, Timisoara and Zerind, and finds Arad → Sibiu → Fagaras → Bucharest, three edges with cost 450. A cheaper route exists (cost 418, four edges) — BFS minimises edges, not cost.

Enter these numbers in the simulator above to see every step.

Complexity and properties

Worst case	$O(b^{d})$
Space	$O(b^{d})$

Complete (finite branching). Optimal only when every step costs the same — it minimises edges, not cost.

When to use it

Finding the shortest path in an unweighted graph or maze.
Level-order traversal of trees.
Comparing uninformed search strategies in AI courses.

Frequently asked questions

What is the time complexity of BFS?

$O(b^{d})$ time and space, where b is the branching factor and d the depth of the shallowest goal. On a graph it is $O(V + E)$ .

Is BFS optimal?

BFS finds the path with the fewest edges, so it is optimal only when every step costs the same.

What is the difference between BFS and DFS?

BFS uses a queue and explores level by level; DFS uses a stack and dives deep first. BFS needs more memory but finds the shallowest goal.