4.3.1 Graph Traversal — AQA 7517

Graph Traversal

Graph traversal algorithms systematically visit every vertex in a graph exactly once. The two main algorithms are Breadth-First Search (BFS) and Depth-First Search (DFS).

Breadth-First Search (BFS)

BFS explores a graph level by level — visiting all neighbours of the current vertex before moving deeper. BFS uses a queue.

BFS Algorithm

// BFS from start node S
1. Create a QUEUE and add S to it
2. Mark S as visited
3. WHILE queue is not empty:
   a. Dequeue the front vertex V
   b. Process V (output it)
   c. FOR each unvisited neighbour N of V:
        Mark N as visited
        Enqueue N
4. END WHILE

BFS Trace Example

// Graph edges: A-B, A-C, B-D, B-E, C-F
// BFS from A:
Queue: [A]       → dequeue A → visit A, enqueue B,C
Queue: [B,C]     → dequeue B → visit B, enqueue D,E
Queue: [C,D,E]   → dequeue C → visit C, enqueue F
Queue: [D,E,F]   → dequeue D → visit D
Queue: [E,F]     → dequeue E → visit E
Queue: [F]       → dequeue F → visit F
Order: A, B, C, D, E, F

BFS Applications

Finding the shortest path in an unweighted graph
Web crawlers
Social network friend-of-friend searches
Broadcasting in networks

Depth-First Search (DFS)

DFS explores a graph by going as deep as possible along one path before backtracking. DFS uses a stack (or recursion).

DFS Algorithm (iterative)

// DFS from start node S
1. Create a STACK and push S onto it
2. WHILE stack is not empty:
   a. Pop top vertex V from stack
   b. IF V not visited:
        Mark V as visited
        Process V (output it)
        FOR each unvisited neighbour N of V:
             Push N onto stack
3. END WHILE

DFS Trace Example

// Same graph: A-B, A-C, B-D, B-E, C-F
// DFS from A (using stack):
Stack: [A]      → pop A → visit A, push C,B (reverse neighbour order)
Stack: [C,B]    → pop B → visit B, push E,D
Stack: [C,E,D]  → pop D → visit D
Stack: [C,E]    → pop E → visit E
Stack: [C]      → pop C → visit C, push F
Stack: [F]      → pop F → visit F
Order: A, B, D, E, C, F

DFS Applications

Maze solving
Topological sorting
Detecting cycles in a graph
Solving puzzles (backtracking)

BFS vs DFS Comparison

Feature	BFS	DFS
Data structure	Queue (FIFO)	Stack (LIFO) or recursion
Exploration order	Level by level (breadth)	Deep first, then backtrack
Shortest path (unweighted)	Yes	No
Memory	Higher (stores all level nodes)	Lower (one path at a time)
Finds all nodes?	Yes	Yes

Exam tip: Know the data structure used by each algorithm — queue for BFS, stack for DFS. Be able to trace both algorithms on a given graph, listing vertices in visit order. Know which gives shortest path in unweighted graphs (BFS). Know practical applications of each.

▶

Click through the slides at your own pace. Use arrow keys or click to advance.

Click slide or press arrow keys to navigate

Worksheet — 4.3.1 Graph Traversal

8 questions · instantly marked · AQA 7517 standard

Q1What data structure does BFS use? What data structure does DFS use?[2]

✅ Mark scheme

Mark scheme

BFS uses a queue (FIFO) [1]; DFS uses a stack (LIFO) or recursion [1].

Q2Explain how BFS explores a graph. In what order does it visit nodes?[2]

✅ Mark scheme

Mark scheme

BFS explores level by level — visiting all neighbours of the current vertex before moving to the next level [1]; it visits nodes in order of their distance from the start vertex [1].

Q3A graph has edges: A-B, A-C, B-D, C-D, C-E. Trace BFS starting from A, showing queue states.[4]

✅ Mark scheme

Mark scheme

Start: queue=[A], visited={A} [1]; Dequeue A, enqueue B,C: queue=[B,C], visit A [1]; Dequeue B, enqueue D: queue=[C,D], visit B [1]; Dequeue C, enqueue E (D already visited): queue=[D,E], visit C; Dequeue D, visit D; Dequeue E, visit E. Order: A,B,C,D,E [1].

Q4Trace DFS on the same graph (A-B, A-C, B-D, C-D, C-E) starting from A.[3]

✅ Mark scheme

Mark scheme

Push A; pop A visit A, push C,B; pop B visit B, push D; pop D visit D (no new neighbours); pop C visit C, push E (D already visited); pop E visit E [2]; Order: A, B, D, C, E (or A, C, E, D, B depending on push order) [1].

Q5Which traversal algorithm finds the shortest path in an unweighted graph? Explain why.[2]

✅ Mark scheme

Mark scheme

BFS finds the shortest path [1]; because it explores level by level — the first time it reaches a vertex is via the shortest path (fewest edges) [1].

Q6Give two real-world applications of BFS and one of DFS.[3]

✅ Mark scheme

Mark scheme

BFS: social network friend suggestions [1]; web crawling [1] (or: shortest route finding in unweighted maps); DFS: maze solving / cycle detection / topological sorting [1].

Q7Why is it important to mark vertices as visited during graph traversal?[2]

✅ Mark scheme

Mark scheme

To prevent visiting the same vertex more than once [1]; without marking, graphs with cycles would cause infinite loops [1].

Q8Compare memory usage of BFS and DFS on a wide shallow graph (many branches, few levels).[2]

✅ Mark scheme

Mark scheme

BFS stores all nodes at the current level in its queue — for a wide graph this requires a lot of memory [1]; DFS only stores one path at a time in its stack — less memory for wide graphs [1].

Topic Quiz

Question 1 of 15

You scored

out of 15

Card 1 of 8

Click to reveal definition

🎉

All cards reviewed!

Term	Definition

Graph Traversal

Breadth-First Search (BFS)

BFS Algorithm

BFS Trace Example

BFS Applications

Depth-First Search (DFS)

DFS Algorithm (iterative)

DFS Trace Example

DFS Applications

BFS vs DFS Comparison

Worksheet — 4.3.1 Graph Traversal

Mini Test — Graph Traversal