Skip to content
Tutorials Center
My learning

Topics

Lesson 122 of 225 ยท Graphs

Breadth-First Search

Learn breadth-first search in Python: queue and visited set, levels, shortest paths in unweighted graphs, path reconstruction, grid mazes and O(V+E) complexity.

Drop a pebble in a pond and watch the ripples. First the water one step from the pebble moves, then two steps away, then three. Breadth-first search (BFS) explores a graph the same way: it visits the start vertex, then everything one edge away, then everything two edges away, and so on, always finishing a distance before starting the next.

That "closest first" order is why BFS finds the shortest path in an unweighted graph: the first time it reaches a vertex, it got there using the fewest possible edges. You saw this on trees as level-order traversal. A general graph can have cycles, so we add a visited set to avoid going around forever. If you need a refresher on how graphs are stored, see Graph Representations.

The algorithm

BFS needs two things: a queue (first in, first out; use collections.deque, see queues) and a visited set.

graph LR
    S((S)) --> A((A))
    S --> B((B))
    A --> C((C))
    A --> D((D))
    B --> D
    D --> E((E))

Breadth-first search from S visits the graph level by level: S first, then A and B, then C and D, and finally E.

  1. Put the start vertex in the queue and mark it visited.
  2. Take the vertex at the front of the queue.
  3. For each neighbor that is not visited: mark it visited and add it to the back of the queue.
  4. Repeat from step 2 until the queue is empty.
TEXT
graph:        0 --- 1 --- 3
              |     |
              2     4
               \   /
                 5 --- 6

start = 0

queue (front -> back)        visited order
[0]                          0
[1, 2]                       0 1 2           (1 and 2 discovered from 0)
[2, 3, 4]                    0 1 2 3 4       (3 and 4 discovered from 1)
[3, 4, 5]                    ...             (5 discovered from 2)
[4, 5]  [5]  [6]  []         0 1 2 3 4 5 6

Vertices are marked visited when they are added to the queue, not when they are removed. That way each vertex is queued at most once.

Python BFS visiting order

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.

Watch out: never use list.pop(0) as a queue. It shifts every remaining element, so each removal costs O(n). deque.popleft() is O(1). For big graphs this single choice decides whether your BFS is linear or quadratic.

Distances and levels

Because BFS processes vertices in order of distance, we can record the distance when we discover each vertex: a neighbor of u is one step farther than u. A dictionary of distances also doubles as the visited set (a vertex is visited if it has a distance).

Python Distances from the start vertex

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.

Vertices that never appear in dist are unreachable from the start. That is a built-in way to test connectivity.

Recovering the actual path

Distances say how far; often you need which route. Store a parent for each vertex: the vertex we came from when we discovered it. After BFS, walk from the target back to the start through the parents and reverse the result.

TEXT
parent: {0: None, 1: 0, 2: 0, 3: 1, 4: 1, 5: 2, 6: 5}

path to 6:  6 -> 5 -> 2 -> 0     reversed:  0 -> 2 -> 5 -> 6
Python Shortest path with parent pointers

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.

When several routes tie for shortest, BFS returns just one of them; which one depends on the order of the neighbor lists. Every route it returns has the minimum number of edges: the path from 3 to 6 above uses 4 edges, and no route with fewer edges exists.

BFS on a grid

Mazes are the classic BFS exercise. Each open cell is a vertex; neighbors are the four adjacent cells that are not walls. The distance to a cell is the minimum number of steps from the start.

Python Shortest path through a maze

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.

Word ladder: BFS on an implicit graph

"Change one letter at a time, each step must be a real word." The shortest ladder is a shortest path where words are vertices and one-letter changes are edges, the graph from Graphs. BFS finds the minimum number of steps.

Python Word ladder 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.

Generating neighbors on the fly (26 letters times word length) avoids building the whole graph first.

Marking visited too late

A very common bug is to mark a vertex visited only when it is removed from the queue. In a graph with many paths to the same vertex the queue then fills with duplicates. Let's count queue insertions in a "ladder" graph where each rung connects to the next two:

Python Mark on push versus mark on pop

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.

Marking on push gives exactly one insertion per vertex (20). Marking on pop still visits every vertex, but it queued 75 entries, almost four times as many, because a vertex is added again by every neighbor that reaches it before it is processed. In the worst case the queue can grow to O(E) entries instead of O(V). Mark when you enqueue.

Complexity

With an adjacency list:

  • Time: O(V + E). Every vertex enters the queue once (O(V)), and when it is dequeued we scan its neighbor list, so every edge is looked at once from each end (in an undirected graph, 2E looks in total).
  • Space: O(V) for the visited set and the queue (in the worst case the queue holds nearly a whole level).

With an adjacency matrix, finding the neighbors of each vertex scans a row, so BFS becomes O(Vยฒ).

Python Counting the work of 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.

When to use BFS (and when not)

Use BFS for: fewest edges between two vertices, shortest path in a grid or maze, distance in "levels" (degrees of separation), spreading processes (multi-source BFS, see connected components and flood fill), testing bipartiteness (bipartite graphs) and checking reachability.

Do not use plain BFS when edges have different weights. It minimizes the number of edges, not the total cost. Use Dijkstra's algorithm for non-negative weights, or 0-1 BFS when weights are only 0 or 1. When you need to explore deeply, or to order tasks, depth-first search fits better.

Common mistakes

  • Using list.pop(0). That is O(n) per removal; use deque.
  • Marking visited too late, which queues the same vertex many times.
  • Forgetting the start vertex in the visited set, so the start is queued again by a neighbor.
  • Only starting from one vertex in a disconnected graph. Loop over all vertices if you need every component.
  • Using BFS for weighted shortest paths. It is only correct when every edge costs the same.
  • Wrong grid bounds. Check 0 <= nr < rows and 0 <= nc < cols before indexing.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

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

    A FIFO queue hands out vertices in the order they were discovered, which is order of increasing distance.
  2. 2. What is the time complexity of BFS on a graph stored as an adjacency list?

    Each vertex is queued once and each edge is examined a constant number of times.
  3. 3. In which situation does BFS give a correct shortest path?

    BFS minimizes the number of edges. It is only a shortest-path algorithm when each edge costs the same.
  4. 4. How do you rebuild the shortest path after BFS finishes?

    Each vertex remembers the vertex that discovered it; walking those links backwards gives the path in reverse.
  5. 5. When should a vertex be marked visited in the standard BFS?

    Marking on insertion guarantees each vertex enters the queue only once.

Summary

  • BFS explores a graph level by level using a queue and a visited set; vertices are marked when queued.
  • It runs in O(V + E) time and O(V) space with an adjacency list.
  • In an unweighted graph the first time BFS reaches a vertex is along a shortest path, so distances and parent pointers give shortest paths.
  • Grids and implicit graphs (word ladders) work the same way with a neighbors rule instead of stored edges.
  • Use deque.popleft(), never list.pop(0).
  • For weighted edges use Dijkstra; for deep exploration or ordering use DFS.

Next: Depth-First Search