Graph traversal: depth-first and breadth-first

Depth-first traversal (DFS)

Uses a stack (or recursion). Visit a vertex, mark it visited, then go to its first unvisited neighbour, and so on; when a vertex has no unvisited neighbours, backtrack.

def dfs(graph, v, visited):
    visited.append(v)
    for w in graph[v]:
        if w not in visited:
            dfs(graph, w, visited)
    return visited

Uses: finding a path, solving mazes, detecting cycles, topological ordering.

Breadth-first traversal (BFS)

Uses a queue. Visit the start vertex and enqueue it; repeatedly dequeue a vertex and enqueue all its unvisited neighbours (marking them visited as they are queued).

from collections import deque
def bfs(graph, start):
    visited, queue = [start], deque([start])
    while queue:
        v = queue.popleft()
        for w in graph[v]:
            if w not in visited:
                visited.append(w)
                queue.append(w)
    return visited

Uses: shortest path by number of edges in an unweighted graph, finding everything within k steps (friends of friends), web crawling.

Tracing by hand

Graph: A-B, A-C, B-D, B-E, C-F, E-F, neighbours taken in alphabetical order, starting at A.

Search, insert and delete

• Search for a vertex or value: traverse (DFS or BFS) and stop when found.
• Insert a vertex: add a row and column to the matrix, or a new key with an empty list; insert an edge: set a cell or append to the lists (both lists if undirected).
• Delete an edge: clear the cell or remove it from the lists; delete a vertex: remove its row and column, or its list and every reference to it in other lists.

Worked example

Trace a breadth-first traversal from A on the graph A-B, A-C, B-D, B-E, C-F, E-F (alphabetical order).

1. Visit A; queue [A]. Dequeue A: enqueue B, C. Queue [B, C].
2. Dequeue B: enqueue D, E (A already visited). Queue [C, D, E].
3. Dequeue C: enqueue F. Queue [D, E, F].
4. Dequeue D, E, F: no new vertices.

Answer: A, B, C, D, E, F

Check yourself

1. Which data structure supports a depth-first traversal?
   • Stack
   • Queue
   • Hash table
   • Circular queue
   Show answer

   Stack. Recursion uses the call stack.

2. Which data structure supports a breadth-first traversal?
   • Stack
   • Binary tree
   • Queue
   • Linked list of weights
   Show answer

   Queue. First in, first out gives level-by-level order.

3. Give the depth-first order from A for the graph A-B, A-C, B-D, B-E, C-F, E-F, taking neighbours alphabetically.
   Show answer

   A, B, D, E, F, C. A, then B, then D (dead end, back to B), E, F, then C via F: A, B, D, E, F, C.

4. Give the breadth-first order from C for the same graph, taking neighbours alphabetically.
   Show answer

   C, A, F, B, E, D. C; its neighbours A, F; then A's B; F's E; then B's D: C, A, F, B, E, D.

5. Give the depth-first order from F for the same graph, taking neighbours alphabetically.
   Show answer

   F, C, A, B, D, E. F, C, A, B, D, back up to B, E: F, C, A, B, D, E.

6. Which traversal finds the route with the fewest edges in an unweighted graph?
   • Depth-first
   • Post-order
   • In-order
   • Breadth-first
   Show answer

   Breadth-first. BFS reaches every vertex at distance 1, then 2, and so on.

7. Why do graph traversals keep a list of visited vertices?
   • To sort the vertices
   • Graphs can contain cycles, so without it a traversal could loop forever
   • To calculate edge weights
   • Because trees need it
   Show answer

   Graphs can contain cycles, so without it a traversal could loop forever. Marking visited vertices prevents revisiting.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary and Advanced Level in Computer Science specification (2026), Issue 1
• Pearson Edexcel IAL Computer Science sample assessment materials (Unit 3 paper, resource booklet and mark scheme)

Last updated 8 November 2026. Spotted a mistake? Tell us.