Computer Science · Grade 11

Active learning ideas

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.

• Ontario Curriculum Expectations
• CS.HS.A.3
• CS.HS.A.4

• 25–45 min
• Pairs → Whole Class
• 4 activities

Activity 01

• 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.

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.

What to look for

Provide students with a small, unweighted graph represented by an adjacency list. Ask them to trace the execution of BFS starting from a specific node, listing the order nodes are visited and the contents of the queue at each step. Then, ask them to do the same for DFS.

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

Activity 02

• 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.

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.

What to look for

Pose the following scenario: 'Imagine you are designing a system to detect if a user has access to a specific file in a complex directory structure. Which traversal algorithm, BFS or DFS, would be more efficient and why? Consider the potential depth of the directory structure.'

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

Activity 03

• 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.

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.

What to look for

On a slip of paper, have students write down one key difference between BFS and DFS in terms of their exploration strategy. Then, ask them to name one specific application where BFS is preferred over DFS, and one where DFS is preferred over BFS.

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

Activity 04

• 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.

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.

What to look for

Provide students with a small, unweighted graph represented by an adjacency list. Ask them to trace the execution of BFS starting from a specific node, listing the order nodes are visited and the contents of the queue at each step. Then, ask them to do the same for DFS.

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

A few notes on teaching this unit

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.

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

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

  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.

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

  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.

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

  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.

---

Methods used in this brief

• Collaborative Problem-Solving