Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 36 ยท Connectivity and Paths

Breadth-First Search

Learn breadth-first search step by step: the queue-based algorithm, shortest paths in unweighted graphs, level structure, path reconstruction and O(n + m) running time, in Python.

How do you explore a graph without missing anything and without going in circles? Breadth-first search (BFS) explores in widening rings: first the start vertex, then all its neighbors, then all vertices two steps away, and so on. Like a ripple spreading from a stone dropped in water, BFS reaches every vertex in the order of its distance from the start.

That order is exactly what makes BFS the standard tool for shortest paths in unweighted graphs: GPS "fewest turns", the fewest handshakes between two people, the fewest moves to solve a puzzle.

The algorithm

BFS uses a queue (first in, first out) and a set of visited vertices.

  1. Put the start vertex s into the queue and mark it visited, with distance 0.
  2. While the queue is not empty, remove the front vertex u.
  3. For every neighbor w of u that is not visited: mark it visited, set dist[w] = dist[u] + 1, remember parent[w] = u, and add w to the back of the queue.

Marking vertices as visited when they enter the queue (not when they leave) is what prevents duplicates.

graph LR
  s --- a
  s --- b
  a --- c
  b --- c
  b --- d
  c --- e
  d --- e

From s: level 0 is {s}, level 1 is {a, b}, level 2 is {c, d}, level 3 is {e}.

Python BFS with distances and parents

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why BFS finds shortest paths

When BFS removes a vertex of distance k from the queue, all vertices at distance k are ahead of those at distance k+1: the queue always holds vertices of at most two consecutive levels, in non-decreasing order. So the first time a vertex is discovered, it is discovered through a path with the fewest edges. The parent pointers then form a BFS tree that encodes one shortest path to every reachable vertex.

To get the path to a target, follow parents backwards and reverse:

Python Reconstructing a shortest path

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Running time

Each vertex is enqueued at most once and each adjacency list is scanned once, so BFS takes O(n + m) time with an adjacency list, and O(nยฒ) with an adjacency matrix (each row scan costs O(n)). The memory is O(n) for the queue, distances and parents.

What BFS gives you for free

  • Distances from the source to all vertices.
  • Reachability: vertices never reached are in other components.
  • Bipartiteness: color levels alternately; an edge inside one level (or between levels with the same parity) means an odd cycle.
  • Layers for problems such as "how many people are within three hops?".
  • Connectivity and the components.
Python Grid maze with BFS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A maze is a graph in disguise: each open cell is a vertex and neighboring open cells are adjacent. Many puzzle and game problems are shortest paths on an implicit graph.

Common mistakes

  • Using a list as a queue (pop(0) is O(n)). Use collections.deque.
  • Marking visited when you dequeue. The same vertex can then enter the queue many times and the algorithm slows down badly.
  • Using BFS for weighted graphs. BFS minimizes edges, not total weight; use Dijkstra.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which data structure drives breadth-first search?

    A FIFO queue processes vertices in the order they were discovered, i.e. by increasing distance.
  2. 2. What is the running time of BFS on an adjacency list?

    Each vertex is enqueued once and each edge examined a constant number of times.
  3. 3. BFS from a source computes shortest paths measured in:

    BFS ignores weights; it minimizes the number of edges on the path.
  4. 4. When should a vertex be marked visited in BFS?

    Marking at enqueue time guarantees every vertex enters the queue at most once.

Summary

  • BFS explores by distance levels using a queue and a visited set.
  • It computes shortest (fewest-edge) paths from the source and a BFS tree of parents.
  • Running time is O(n + m) with adjacency lists.
  • Mazes, puzzles and "degrees of separation" are all BFS problems.
  • Use a deque, mark vertices at enqueue time, and switch to Dijkstra for weights.

Next: Depth-First Search