Graphs: Traversal Algorithms (BFS/DFS)

Active learning helps students grasp graph traversal because the abstract concepts of queues and stacks become concrete when they physically simulate or code them. Watching neighbors expand or branches explore in real time builds intuition that static diagrams cannot match.

• Grade 11
• Computer Science
• 4 activities
• 25 min–45 min

Learning Objectives

1. Compare the step-by-step exploration strategies of Breadth-First Search (BFS) and Depth-First Search (DFS) when traversing a given graph.
2. Analyze the time and space complexity of BFS and DFS algorithms for both adjacency list and adjacency matrix representations of a graph.
3. Design and implement an algorithm using BFS to find the shortest path between two nodes in an unweighted graph.
4. Evaluate the suitability of BFS versus DFS for specific graph problems, such as finding cycles or determining connectivity.

Collaborative Problem-Solving

⏱ 35 min·Pairs

Pair Programming: BFS Maze Challenge

Pairs sketch a simple grid graph as a maze, then code BFS to find the shortest path from start to goal. Switch roles for DFS version and compare paths printed from code. Discuss why paths differ.

Prepare & details

Differentiate between BFS and DFS in terms of their exploration strategy and applications.

Facilitation Tip: During Pair Programming: BFS Maze Challenge, rotate pairs randomly halfway through so students see different approaches to the same maze.

Setup: Groups at tables with problem materials

Materials: Problem packet, Role cards (facilitator, recorder, timekeeper, reporter), Problem-solving protocol sheet, Solution evaluation rubric

• Apply
• Analyze
• Evaluate
• Create
• Relationship Skills
• Decision-Making
• Self-Management

Collaborative Problem-Solving

⏱ 45 min·Small Groups

Small Groups: Complexity Comparison Lab

Groups generate sparse and dense graphs using adjacency lists. Implement BFS and DFS, measure execution time and memory on 100+ nodes. Chart results and predict for larger graphs.

Prepare & details

Analyze the time and space complexity of BFS and DFS on different graph structures.

Facilitation Tip: In Small Groups: Complexity Comparison Lab, assign each group a different graph size to test scalability, then compile class results on the board.

Setup: Groups at tables with problem materials

Materials: Problem packet, Role cards (facilitator, recorder, timekeeper, reporter), Problem-solving protocol sheet, Solution evaluation rubric

• Apply
• Analyze
• Evaluate
• Create
• Relationship Skills
• Decision-Making
• Self-Management

Collaborative Problem-Solving

⏱ 30 min·Whole Class

Whole Class: Live Traversal Simulation

Project a graph on the board. Class votes on next node for BFS queue or DFS stack. Code live in Python, pausing for predictions. Replay with different starts.

Prepare & details

Construct an algorithm to find the shortest path in an unweighted graph using BFS.

Facilitation Tip: For Whole Class: Live Traversal Simulation, use a large floor grid and have students physically stand in visited nodes to reinforce BFS layering and DFS branching.

Setup: Groups at tables with problem materials

Materials: Problem packet, Role cards (facilitator, recorder, timekeeper, reporter), Problem-solving protocol sheet, Solution evaluation rubric

• Apply
• Analyze
• Evaluate
• Create
• Relationship Skills
• Decision-Making
• Self-Management

Collaborative Problem-Solving

⏱ 25 min·Individual

Individual: Custom Graph Tester

Students build personal graphs from real scenarios like friend networks. Code both algorithms, output traversal orders, and note applications in a reflection log.

Prepare & details

Differentiate between BFS and DFS in terms of their exploration strategy and applications.

Facilitation Tip: With Individual: Custom Graph Tester, provide starter code with intentional bugs so students practice debugging traversals, not just writing them from scratch.

Setup: Groups at tables with problem materials

Materials: Problem packet, Role cards (facilitator, recorder, timekeeper, reporter), Problem-solving protocol sheet, Solution evaluation rubric

• Apply
• Analyze
• Evaluate
• Create
• Relationship Skills
• Decision-Making
• Self-Management

Teaching This Topic

Start with physical simulations to build intuition, then move to code so students see how abstract data structures drive behavior. Avoid rushing to implementation; spend time tracing small examples together on paper first. Research shows that alternating between hands-on tracing and coding deepens understanding more than either method alone.

What to Expect

Successful learning looks like students confidently explaining why BFS or DFS fits a problem, tracing traversals accurately on paper, and justifying their algorithm choice based on graph structure. They should also compare time and space complexities with evidence from their own code runs.

Watch Out for These Misconceptions

Common Misconception

During Pair Programming: BFS Maze Challenge, watch for students assuming BFS and DFS always visit nodes in the same order regardless of starting point.

What to Teach Instead

Have pairs swap their maze printouts and trace each other’s step-by-step prints, highlighting how the queue’s level-by-level order differs from DFS’s branch-by-branch order.

Common Misconception

During Small Groups: Complexity Comparison Lab, watch for students claiming DFS finds shortest paths faster than BFS in all cases.

What to Teach Instead

Ask groups to time both algorithms on the same maze and record path lengths; then facilitate a gallery walk where groups post their evidence and debate why BFS guarantees shortest unweighted paths.

Common Misconception

During Whole Class: Live Traversal Simulation, watch for students attributing stack overflow in DFS to recursion itself rather than graph depth.

What to Teach Instead

Use physical cards to simulate the call stack, adding one card per recursive step until students see that overflow only happens when the stack exceeds memory, not from recursion alone.

Assessment Ideas

Quick Check

After Pair Programming: BFS Maze Challenge, collect each pair’s printed trace of BFS and DFS on their maze. Check that node visit orders match the expected level-by-level and branch-by-branch patterns, and that queue and stack contents are recorded correctly at each step.

Discussion Prompt

During Small Groups: Complexity Comparison Lab, listen for groups to justify their algorithm choice for the file access scenario by citing graph depth versus breadth, and note whether they mention worst-case time or space complexity.

Exit Ticket

At the end of Whole Class: Live Traversal Simulation, have students write on a slip one key difference between BFS’s exploration strategy and DFS’s strategy, and name one application where BFS is preferred and one where DFS is preferred.

Extensions & Scaffolding

• Challenge students who finish early to adapt their BFS maze solver to handle weighted edges by converting it to Dijkstra’s algorithm.
• Scaffolding for struggling students: provide pre-printed graph diagrams with numbered nodes so they focus on tracing rather than building graphs from scratch.
• Deeper exploration: ask students to design a hybrid traversal that switches from DFS to BFS when the stack depth exceeds a threshold, and measure its performance on deep graphs.

Key Vocabulary

Graph Traversal	The process of visiting each node in a graph in a systematic way, ensuring no node is missed.
Breadth-First Search (BFS)	A graph traversal algorithm that explores neighbor nodes first before moving to the next level neighbors, typically using a queue.
Depth-First Search (DFS)	A graph traversal algorithm that explores as far as possible along each branch before backtracking, typically using a stack or recursion.
Queue	A First-In, First-Out (FIFO) data structure used in BFS to keep track of nodes to visit next.
Stack	A Last-In, First-Out (LIFO) data structure used in DFS (iterative implementation) to keep track of nodes to visit next.