0

Breadth First Search

Medium

Explore in rings of increasing distance. The first time BFS reaches a node, it arrived by a shortest path.

queueshortest pathunweighted
TimeO(V + E)
SpaceO(V)
Inputedges like 0-1,1-2 | start node
0012345
queue
0

Start BFS at node 0. Distance to itself is 0.

1 / 22
queue = [start]; dist[start] = 0
while queue not empty:
u = queue.pop_front()
for v in adj[u]:
if v not visited:
dist[v] = dist[u] + 1; queue.push(v)
Why it matters

Mark nodes visited when you enqueue them, not when you dequeue, or they enter the queue twice.

Practise this
Number of IslandsMRotting OrangesMWord LadderH01 MatrixM
Keyboard
space play← → stepr restartctrl K search

More in Graphs

Depth First Search
O(V + E)
Dijkstra Shortest Path
O(E log V)
Topological Sort (Kahn)
O(V + E)
Union-Find (DSU)
Near O(1) amortised per operation
Kruskal Minimum Spanning Tree
O(E log E)
Flood Fill / Number of Islands
O(rows * cols)
Next visualiser
Depth First Search