Graph Traversal: BFS and DFS in Algorithms | OCR H446

Learning Objectives

By the end of this topic you will be able to:

Describe and trace BFS using a queue, showing the visited set and queue state at each step

Describe and trace DFS using a stack (or recursion), showing the visited set and stack state

Identify applications of BFS and DFS in real-world computing contexts

Explain the time and space complexity of BFS and DFS

Graph Recap

Graph Structure for Traversal

Graph G (adjacency list):
A → [B, C]
B → [A, D, E]
C → [A, F]
D → [B]
E → [B, F]
F → [C, E]

BFS — uses Queue

Explores all neighbours of current node before moving deeper. Level-by-level. Start → distance 1 nodes → distance 2 nodes → ...

DFS — uses Stack

Explores as deep as possible along each branch before backtracking. Start → go as deep as possible → backtrack when stuck.

BFS Algorithm

Breadth-First Search: Pseudo-Code

procedure BFS(graph, start)
  visited ← empty set
  queue ← [start]
  add start to visited
  while queue is not empty
    node ← dequeue(queue)
    process(node)
    for each neighbour of node
      if neighbour not in visited then
        add neighbour to visited
        enqueue(neighbour)
      endif
    next
  endwhile
endprocedure

BFS Trace

Tracing BFS from Node A

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

Step-by-step BFS

Queue: [A] | Visited: {A}
Dequeue A → process A; enqueue B,C → Queue:[B,C] | Visited:{A,B,C}
Dequeue B → process B; D,E not visited → Queue:[C,D,E] | Visited:{A,B,C,D,E}
Dequeue C → process C; F not visited → Queue:[D,E,F] | Visited:{A,B,C,D,E,F}
Dequeue D → process D; B already visited → Queue:[E,F]
Dequeue E → process E; B,F already visited → Queue:[F]
Dequeue F → process F → Queue:[]
Order visited: A, B, C, D, E, F

DFS Algorithm

Depth-First Search: Pseudo-Code

procedure DFS(graph, start)
  visited ← empty set
  stack ← [start]
  while stack is not empty
    node ← pop(stack)
    if node not in visited then
      add node to visited
      process(node)
      for each neighbour of node
        if neighbour not in visited then
          push(neighbour, stack)
        endif
      next
    endif
  endwhile
endprocedure

Applications & Complexity

When to Use BFS vs DFS

BFS Applications

Shortest path (unweighted graphs); social network "degrees of separation"; web crawlers (crawl breadth-first); broadcasting in networks; finding all nodes within k hops

DFS Applications

Detecting cycles; topological sort (scheduling); solving mazes; connected components; backtracking puzzles (Sudoku, N-Queens); compiler syntax analysis

Complexity — Both BFS and DFS

Time: O(V+E) using adjacency list — each vertex and each edge is processed once
Space: BFS O(V) in worst case (queue stores all nodes at current level); DFS O(V) for stack/call stack in worst case (linear graph)

Exam Practice

OCR H446 Style · 5 marks

Using the graph below, show the order of nodes visited using BFS starting from node 1, and show the queue state at each step.
1→[2,3], 2→[1,4,5], 3→[1,6], 4→[2], 5→[2], 6→[3]

[5 marks]

Queue:[1] Visited:{1}
Dequeue 1 → enqueue 2,3 → Queue:[2,3] Visited:{1,2,3}
Dequeue 2 → enqueue 4,5 (1 already visited) → Queue:[3,4,5] Visited:{1,2,3,4,5}
Dequeue 3 → enqueue 6 (1 already visited) → Queue:[4,5,6] Visited:{1,2,3,4,5,6}
Dequeue 4 → Queue:[5,6] (2 already visited)
Dequeue 5 → Queue:[6] (2 already visited)
Dequeue 6 → Queue:[]
Order: 1, 2, 3, 4, 5, 6

Common Mistakes

Don't Lose Marks

Not maintaining a visited set in BFS/DFS — without tracking visited nodes, the algorithm revisits nodes, potentially looping forever in a cyclic graph. Always add nodes to the visited set when they are first discovered (for BFS) or when processed (for DFS). This must be stated or shown in your trace.

Confusing when nodes are added to visited in BFS vs DFS — in BFS, nodes are added to visited when enqueued (not when dequeued), to prevent duplicates in the queue. In DFS using a stack, nodes are added when popped. Getting this wrong produces incorrect traversal orders.

Claiming DFS uses a queue or BFS uses a stack — fundamental error. BFS uses a QUEUE (FIFO — explore layer by layer). DFS uses a STACK (LIFO — explore depth-first). Reversing these will give completely wrong traversal orders in trace questions.

Graph Traversal:BFS and DFSin Algorithms