Breadth-First Search

Explore a graph layer by layer using a queue. Guarantees shortest path in an unweighted graph because nodes are visited in order of their distance from the source.

time O(V + E)

space O(V)

Input

Press Tab out of the box or click Resetto regenerate frames from the current input.

Visualization

No frames yet — edit input and click Run.

—

Pseudocode

queue = [start]
visited = {start}
while queue:
  u = queue.popleft()
  for v in neighbours(u):
    if v not in visited:
      visited.add(v); queue.append(v)