3.2Breadth-first search
The idea
Breadth-first search explores a graph level by level using a queue, finding shortest paths by edge count.
Think of it like this: A ripple in a pond: everything one step away is reached first, then two steps away.
Why it exists
BFS answers shortest-hop and bipartiteness questions.
How it works
- Enqueue the start vertex and mark it.
- Dequeue a vertex, look at each unvisited neighbour.
- Mark, set its distance + 1, enqueue it.
- Repeat until the queue is empty.
Worked example: BFS from A in the sample graph
Distances: A 0; B, D 1; C, E, G 2; F 3. Time O(V + E).
Now play with it
- →Step through the algorithm and watch the queue.
- →Note that tree edges (green) give shortest paths.
Yellow = waiting, white fill = current, green = finished. Thick green edges are tree / MST edges.
- enqueue A
- dequeue A, scan its neighbours
- B is new: dist 1, enqueue
- D is new: dist 1, enqueue
- dequeue B, scan its neighbours
- C is new: dist 2, enqueue
- E is new: dist 2, enqueue
- dequeue D, scan its neighbours
- G is new: dist 2, enqueue
- dequeue C, scan its neighbours
- F is new: dist 3, enqueue
- dequeue E, scan its neighbours
- dequeue G, scan its neighbours
- dequeue F, scan its neighbours
- queue empty: BFS finished (O(V + E)); tree edges give shortest hop counts
Uses a queue. Time O(V + E). The BFS tree gives shortest paths in an unweighted graph.
Check yourself
BFS on a graph with adjacency lists runs in
Exam notes (the dense version)
BFS uses a queue and explores vertices level by level. Time O(V + E) with lists (O(V²) with a matrix). The BFS tree gives shortest paths in an unweighted graph. Uses: shortest hop count, connected components, testing bipartiteness (2-colour by level), finding the shortest cycle.
Previous year questions: Graph Algorithms (35)
PYQs are grouped by topic, so this is the full set for Graph Algorithms; try the ones that match this subtopic. Open all 35 on the topic page.