Data Structures, Lecture 7: Graph traversal with BFS and DFS
Course: CS 201 Data Structures · Lecture: 7 of 24 · Author: Dr. Meera Iyer · Date: 14 Oct 2026
Note
These notes are shared view-only. Use File → Make a copy to get your own private copy, then tick off the problems, highlight and comment as you revise.
Learning objectives
By the end of this lecture you should be able to:
- Represent a graph as an adjacency list and as an adjacency matrix, and say when each is the better choice.
- Trace breadth-first search (BFS) and depth-first search (DFS) by hand on a small graph.
- Prove that BFS runs in
O(V + E)time on an adjacency list. - Use BFS to find shortest paths in an unweighted graph.
Before you start
- Queues and stacks (Lecture 4).
- Big O notation (Lecture 2).
Key ideas
A graph is vertices plus edges
A graph G = (V, E) is a set of vertices V and a set of edges E, each edge joining two vertices. We write |V| as V and |E| as E when it is clear from context. In an undirected graph E \le V(V-1)/2.
Two ways to store it
An adjacency list keeps, for each vertex, the list of its neighbours. It needs \Theta(V + E) memory. An adjacency matrix is a V \times V grid of zeros and ones and needs \Theta(V^2) memory, but answers "is there an edge from u to v?" in O(1). For a sparse graph such as a road network, where E is close to V, the list wins by a wide margin.
BFS explores in rings, DFS dives deep
BFS visits every vertex at distance 1 from the start, then every vertex at distance 2, and so on, using a queue. DFS follows one path as far as it can before backing up, using a stack (or recursion, which uses the call stack).
Definitions
| Term | Definition |
|---|---|
| Degree | The number of edges touching a vertex. In an undirected graph the degrees add up to 2E. |
| Path | A sequence of vertices where each consecutive pair is joined by an edge. |
| Connected | An undirected graph is connected when there is a path between every pair of vertices. |
| BFS tree | The edges BFS used to discover each vertex for the first time. |
The main result
BFS on an adjacency list visits every vertex once and looks at every edge at most twice (once from each end in an undirected graph), so
T_{\text{BFS}}(V, E) = O(V) + O\left(\sum_{v \in V} \deg(v)\right) = O(V + 2E) = O(V + E)
DFS has the same bound for the same reason. On an adjacency matrix both take O(V^2), because finding the neighbours of one vertex means scanning a whole row.
Diagram
The graph we traced in class, with BFS starting from A:
flowchart LR
A["A (0)"] --- B["B (1)"]
A --- C["C (1)"]
B --- D["D (2)"]
C --- D
C --- E["E (2)"]
D --- F["F (3)"]
The number in brackets is each vertex's distance from A, which is exactly the ring BFS finds it in.
Worked example
Problem. Run BFS from A on the graph above. Give the visiting order and the distance to every vertex. Break ties alphabetically.
Solution.
- Start: queue = [A], dist(A) = 0.
- Take A. Its unvisited neighbours are B and C, so dist(B) = dist(C) = 1. Queue = [B, C].
- Take B. Its unvisited neighbour is D, so dist(D) = 2. Queue = [C, D].
- Take C. D is already discovered, E is new, so dist(E) = 2. Queue = [D, E].
- Take D. F is new, so dist(F) = 3. Queue = [E, F].
- Take E, then F. Neither has an undiscovered neighbour. The queue is empty, so we stop.
Answer. Visiting order A, B, C, D, E, F. Distances A 0, B 1, C 1, D 2, E 2, F 3.
The same algorithm in Python:
from collections import deque
def bfs(graph, start):
dist = {start: 0}
queue = deque([start])
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in sorted(graph[u]):
if v not in dist:
dist[v] = dist[u] + 1
queue.append(v)
return order, dist
Try it
Solution
A, B, D, C, E, F. From A go to B, from B to D, from D the smallest unvisited neighbour is C, from C go to E. E has no unvisited neighbour, so back up to D and visit F.
Solution
The matrix needs V^2 = 10^8 cells. The list needs V + 2E = 10{,}000 + 60{,}000 = 70{,}000 entries for an undirected graph. The list is more than a thousand times smaller.
Solution
BFS removes vertices from the queue in order of distance, so the first time it discovers a vertex it has come by a path with the fewest possible edges. DFS can reach a vertex first by a long detour, as it does with C in Problem 1 (reached through B and D, distance 3 along that path, while the true distance is 1).
Common mistakes
- Marking a vertex visited when it is taken off the queue instead of when it is put on. The vertex can then be queued twice.
- Quoting
O(V^2)for BFS without saying which representation. The bound depends on it. - Forgetting disconnected graphs: one BFS only reaches the start vertex's component.
Summary
- Adjacency list:
\Theta(V + E)memory, best for sparse graphs. - BFS uses a queue and finds shortest paths by edge count.
- DFS uses a stack or recursion and is the basis of cycle detection and topological sort (Lecture 8).
- Both run in
O(V + E)on an adjacency list.
Further reading
- Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 4th edition, Sections 20.1 to 20.3.
- Sedgewick and Wayne, Algorithms, 4th edition, Section 4.1.