Graph Traversal

This lesson covers breadth-first search (BFS) and depth-first search (DFS) — the two fundamental algorithms for traversing (visiting) all vertices in a graph. Both are required by the OCR A-Level Computer Science (H446) specification.

---

What is Graph Traversal?

Graph traversal is the process of visiting every vertex in a graph exactly once, starting from a given source vertex. The two main strategies differ in the order in which vertices are visited.

Algorithm	Strategy	Data Structure	Explores
BFS	Visit all neighbours before going deeper	Queue	Level by level
DFS	Go as deep as possible before backtracking	Stack (or recursion)	Branch by branch

---

Breadth-First Search (BFS)

BFS explores a graph level by level — it visits all vertices at distance 1 from the start, then distance 2, then distance 3, and so on.

Algorithm

1. Start at the source vertex. Mark it as visited and add it to a queue.
2. While the queue is not empty: a. Dequeue the front vertex. b. Process (visit) this vertex. c. For each unvisited neighbour of this vertex:
   • Mark it as visited.
   • Enqueue it.

Pseudocode (OCR Style)

procedure bfs(graph, start)
    queue = new Queue()
    visited = new Set()
    queue.enqueue(start)
    visited.add(start)
    while NOT queue.isEmpty()
        vertex = queue.dequeue()
        print(vertex)
        for each neighbour of vertex in graph
            if neighbour NOT in visited then
                visited.add(neighbour)
                queue.enqueue(neighbour)
            endif
        next neighbour
    endwhile
endprocedure

Python Implementation

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    result = []

    while queue:
        vertex = queue.popleft()
        result.append(vertex)
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)

    return result

Worked Example

Graph (adjacency list):

A: [B, C]
B: [A, D, E]
C: [A, F]
D: [B]
E: [B, F]
F: [C, E]

BFS starting from A:

Step	Queue (front -> rear)	Visited	Process
Start	[A]	{A}	-
1	[B, C]	{A, B, C}	A
2	[C, D, E]	{A, B, C, D, E}	B
3	[D, E, F]	{A, B, C, D, E, F}	C
4	[E, F]	{A, B, C, D, E, F}	D
5	[F]	{A, B, C, D, E, F}	E
6	[]	{A, B, C, D, E, F}	F

BFS order: A, B, C, D, E, F

---

Depth-First Search (DFS)

DFS explores as deep as possible along each branch before backtracking. It follows a single path until it reaches a dead end, then backtracks to explore alternative paths.

Algorithm

1. Start at the source vertex. Mark it as visited, push it onto a stack.
2. While the stack is not empty: a. Pop the top vertex. b. If not visited, mark as visited and process it. c. Push all unvisited neighbours onto the stack.

Pseudocode (OCR Style) — Iterative

procedure dfs(graph, start)
    stack = new Stack()
    visited = new Set()
    stack.push(start)
    while NOT stack.isEmpty()
        vertex = stack.pop()
        if vertex NOT in visited then
            visited.add(vertex)
            print(vertex)
            for each neighbour of vertex in graph
                if neighbour NOT in visited then
                    stack.push(neighbour)
                endif
            next neighbour
        endif
    endwhile
endprocedure

Pseudocode — Recursive

procedure dfsRecursive(graph, vertex, visited)
    visited.add(vertex)
    print(vertex)
    for each neighbour of vertex in graph
        if neighbour NOT in visited then
            dfsRecursive(graph, neighbour, visited)
        endif
    next neighbour
endprocedure

Python Implementation (Recursive)