Graph Traversal: Breadth-First Search and Depth-First Search

What Is Graph Traversal?

Graph traversal is the process of visiting every vertex in a graph exactly once. Traversal algorithms are the foundation of many graph algorithms.

Breadth-First Search (BFS)

Strategy

BFS explores a graph layer by layer, visiting all neighbours at distance 1, then distance 2, and so on. It uses a queue (FIFO).

Algorithm

ALGORITHM BFS(graph, start)
    visited ← empty set
    queue ← empty queue

    enqueue(queue, start)
    add start to visited

    while NOT isEmpty(queue) do
        v ← dequeue(queue)
        process(v)
        for each neighbour w of v do
            if w NOT in visited then
                add w to visited
                enqueue(queue, w)
            end if
        end for
    end while

Properties

• Data structure: Queue
• Order: Visits vertices in order of increasing distance from source
• Shortest path: Finds the shortest path (minimum hops) in unweighted graphs
• Time complexity: $O(V + E)$ where $V$ = vertices, $E$ = edges
• Space complexity: $O(V)$ (queue can hold all vertices)

Worked Example

Graph: A–B, A–C, B–D, C–D, D–E. Start: A.

Step 1: Queue = [A], Visited = {A}
Step 2: Dequeue A, enqueue B, C → Queue = [B, C], Visited = {A,B,C}
Step 3: Dequeue B, enqueue D → Queue = [C, D], Visited = {A,B,C,D}
Step 4: Dequeue C, D already visited → Queue = [D], Visited = {A,B,C,D}
Step 5: Dequeue D, enqueue E → Queue = [E], Visited = {A,B,C,D,E}
Step 6: Dequeue E → Queue = [], done
Order: A, B, C, D, E

Depth-First Search (DFS)

Strategy

DFS explores a graph by going as deep as possible along each branch before backtracking. It uses a stack (explicitly or via recursion).

Algorithm (Recursive)

ALGORITHM DFS(graph, v, visited)
    add v to visited
    process(v)
    for each neighbour w of v do
        if w NOT in visited then
            DFS(graph, w, visited)
        end if
    end for

Properties

• Data structure: Stack (implicit via call stack in recursion)
• Order: Explores one branch deeply before exploring others
• Path finding: Can find paths but NOT necessarily shortest paths
• Time complexity: $O(V + E)$
• Space complexity: $O(V)$ (recursion depth / stack size)

Worked Example

Same graph. Start: A.

DFS(A) → process A
  → DFS(B) → process B
      → DFS(D) → process D
          → DFS(C) → process C  (D's neighbour)
              → DFS(E) → process E
Order: A, B, D, C, E (one possible order — depends on adjacency list order)

BFS vs. DFS Comparison

EXAM TIP: BFS uses a queue, DFS uses a stack. This is a frequently tested distinction. Also: BFS finds shortest hop count; Dijkstra’s finds shortest weighted path.

VCAA FOCUS: Be able to trace BFS and DFS on a given graph, showing the order of vertex visits and the queue/stack state at each step.

# BFS in Python
from collections import deque

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