Breadth-First Search

Shortest Path (Unweighted)

In an unweighted graph, the shortest path is simply the path with the minimum number of edges. By exploring the graph layer-by-layer, BFS ensures that every node is reached via its optimal distance.

Time ComplexityO(V + E)

Space ComplexityO(V)

Layer Discovery

BFS visits all nodes at distance k before moving to distance k+1, guaranteeing the shortest path property.

Parent Tracking

By storing the 'parent' of each node (the vertex that discovered it), we can reconstruct the actual shortest path back to the source.

🖱️ Click to Add • ↔️ Drag to Move • ⌨️ Shift+Drag to Join

Loading Lab...

Breadth-First Search

Shortest Path (Unweighted)

In an unweighted graph, the shortest path is simply the path with the minimum number of edges. By exploring the graph layer-by-layer, BFS ensures that every node is reached via its optimal distance.

Time ComplexityO(V + E)

Space ComplexityO(V)

Layer Discovery

BFS visits all nodes at distance k before moving to distance k+1, guaranteeing the shortest path property.

Parent Tracking

By storing the 'parent' of each node (the vertex that discovered it), we can reconstruct the actual shortest path back to the source.

🖱️ Click to Add • ↔️ Drag to Move • ⌨️ Shift+Drag to Join

Shortest Path Unweighted

Shortest Path Unweighted

Shortest Path (Unweighted)

Layer Discovery

Parent Tracking

Shortest Path (Unweighted)

Layer Discovery

Parent Tracking