BFS

O(V + E)

Breadth-first search visits a graph one layer at a time. Starting from a source node it explores all of its direct neighbours, then their neighbours, and so on. A FIFO queue holds the nodes waiting to be visited in arrival order — that is exactly what makes the traversal go level by level, and what lets BFS find the shortest path in an unweighted graph.

Click empty space = vertex · click two vertices = edge · drag = moveStart: A
Input graph
BFS tree
Press ▶ to run
Queue
Press ▶ to run
Edit the input and press Play

How it works

  1. Put the start node in the queue and mark it visited.
  2. Take the node from the front of the queue and process it.
  3. Look at each neighbour; mark every unvisited one and add it to the back of the queue.
  4. Repeat until the queue is empty — every reachable node has been visited.

Pseudocode

1BFS(graph, start):2  visited ← { start }3  queue ← [ start ]4  while queue is not empty:5    node ← queue.dequeue()         # take from the front6    process(node)7    for each neighbour of node:8      if neighbour not in visited:9        visited.add(neighbour)10        queue.enqueue(neighbour)    # add to the back