Breadth-First Search: Visiting a Graph by Distance From the Start

A queue hands out vertices in the order they were found, so every vertex one edge away comes before any vertex two edges away.

Breadth-first search visits every vertex a start vertex can reach, nearest first: all the vertices one edge away, then all those two edges away, and so on. It does that with two things, a queue of vertices found but not yet visited, and a visited set of every vertex already found, so no vertex is added twice. This card traces it on a small graph, says when the mark goes on, and gives its cost.

The graph below is undirected, stored as an adjacency list, and each vertex's neighbours are taken in alphabetical order so the trace is fixed. It is the graph every card in Graph Traversal uses.

The topic's graph: six vertices and seven undirected edges

The loop is short. Put the start in the queue and mark it visited. Then, until the queue is empty, take the vertex at the front, visit it, and add each neighbour that is not yet marked, marking it as it goes in. The steps below are one per vertex taken from the queue, starting from A, and each shows the queue, the visited set and the order of visits after that step, as a run printed them.

Breadth-first search from A, one step per vertex taken from the queue

Take A

A is visited first. Its neighbours B and C are unmarked, so both are marked and join the queue.

text

queue:   B C
visited: A B C
order:   A

Take B

B's neighbours are A and D. A is already marked, so only D joins.

text

queue:   C D
visited: A B C D
order:   A B

Take C

C's neighbours are A, D and E. A and D are marked, so only E joins, behind D.

text

queue:   D E
visited: A B C D E
order:   A B C

Take D

D adds F, the last unmarked vertex. Every vertex is now marked.

text

queue:   E F
visited: A B C D E F
order:   A B C D

Take E

E's neighbours C and F are both marked, so nothing joins.

text

queue:   F
visited: A B C D E F
order:   A B C D E

Take F

F adds nothing and the queue is empty, so the search ends.

text

queue:   (empty)
visited: A B C D E F
order:   A B C D E F

The order is A, then B and C at one edge, then D and E at two, then F at three. The queue gives that order for free: a vertex joins behind every vertex found before it, and the vertices one edge away are all found while A is taken, before any vertex two edges away can be.

The mark goes on when a vertex joins the queue, not when it leaves. While C was taken, D was already waiting, and because it was marked C did not add it a second time. Marking a Vertex Visited When It Leaves the Queue shows what goes wrong the other way.

Think of the ripples from a stone dropped in a pond: the first ring, then the second, each farther out. The picture breaks in one place. A ripple reaches every point at its distance at the same moment, while the queue still hands the vertices of one ring out one at a time, in the order they were found.

Reach for breadth-first search when a problem says fewest steps, fewest moves, levels, or nearest first. Each of those is a question about distance in edges, and breadth-first search answers it in the order it visits.

Breadth-first search on a graph with V vertices and E edges

Time: O(V + E); every vertex joins the queue once, and every adjacency list is read once
Extra space: O(V); the queue and the visited set each hold at most every vertex
Storage it assumes: Adjacency list; an adjacency matrix makes it O(V²), because each row is read in full

On the Algorithms: Graph Algorithms cheatsheet

← → move through sections and cards