Computer Science · Grade 12

Active learning ideas

Graphs: Representation and Traversal

Active learning works for graphs because students struggle to visualize abstract connections until they physically build and traverse them. Creating adjacency lists and matrices by hand, or simulating BFS and DFS with tokens, turns invisible relationships into tangible experiences that reveal why efficiency and order matter in real algorithms.

• Ontario Curriculum Expectations
• CS.DSAA.12
• CS.P.12

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

Activity 01

• Concept Mapping
• 30 min · Pairs

Pairs Coding: Build Adjacency Representations

Pairs draw a sample graph of 6 nodes, then code both adjacency matrix and list versions in Python. They add edges, print structures, and compare space usage by counting non-zero entries. Discuss trade-offs based on graph density.

Compare adjacency matrix and adjacency list representations for graphs.

Facilitation Tip

During Pairs Coding, start with small undirected graphs so students see symmetry in adjacency matrices without getting overwhelmed by direction.

What to look for

Present students with a small graph drawn on the board. Ask them to identify whether an adjacency matrix or an adjacency list would be more memory efficient for this specific graph and to justify their choice in one sentence.

• Understand
• Analyze
• Create
• Self-Awareness
• Self-Management

Activity 02

• Concept Mapping
• 45 min · Small Groups

Small Groups: Token Traversal Simulation

Groups use a printed graph and colored tokens to simulate BFS (queue: FIFO) and DFS (stack: LIFO) from a start node. Record visit order on worksheets, marking paths. Compare results for path existence between pairs of nodes.

Explain the differences between Breadth-First Search (BFS) and Depth-First Search (DFS).

Facilitation Tip

For Token Traversal Simulation, use different colored tokens for visited and unvisited nodes to make the BFS layering and DFS branching visually obvious.

What to look for

Provide students with a simple graph and two nodes, A and B. Ask them to write down the sequence of nodes visited if performing a BFS starting from A, and then the sequence if performing a DFS starting from A. Specify if a stack or recursion is used for DFS.

• Understand
• Analyze
• Create
• Self-Awareness
• Self-Management

Activity 03

• Concept Mapping
• 20 min · Whole Class

Whole Class: Pathfinding Challenge

Project a large graph; class votes on start/end nodes. Teacher facilitates live BFS/DFS on board while students predict and justify visit orders. Groups verify with personal sketches.

Design an algorithm to find if a path exists between two nodes in a graph.

Facilitation Tip

In the Pathfinding Challenge, provide a real-world scenario like a delivery route to ground the abstract problem in a concrete context.

What to look for

Facilitate a class discussion: 'Imagine you need to build a system that checks if every page on a website is reachable from the homepage. Which traversal algorithm, BFS or DFS, would you choose and why? What are the potential pitfalls of the other algorithm in this context?'

• Understand
• Analyze
• Create
• Self-Awareness
• Self-Management

Activity 04

• Concept Mapping
• 25 min · Individual

Individual: Code Path Detection

Students implement a BFS function to check if a path exists between nodes, using a visited array. Test on 3 provided graphs, timing runs for sparse vs. dense cases.

Compare adjacency matrix and adjacency list representations for graphs.

Facilitation Tip

For Code Path Detection, require students to print both the visited order and the final path to reinforce that traversal and path extraction are separate steps.

What to look for

Present students with a small graph drawn on the board. Ask them to identify whether an adjacency matrix or an adjacency list would be more memory efficient for this specific graph and to justify their choice in one sentence.

• Understand
• Analyze
• Create
• Self-Awareness
• Self-Management

A few notes on teaching this unit

Teach this topic by alternating between concrete construction and abstract reasoning: build graphs by hand first, then code them, then analyze their properties. Avoid rushing to code; let students count edges and measure matrix cells before they write loops. Use analogies students already know, like city maps for adjacency matrices and social networks for adjacency lists. Research shows that students retain graph algorithms better when they first experience them physically before formalizing them into code.

Students should confidently choose the right graph representation for a task and explain their choice based on memory and edge density. They should also distinguish BFS from DFS by describing order, purpose, and implementation, and apply these traversals to solve pathfinding problems in new contexts.

---

Watch Out for These Misconceptions

• During Pairs Coding: Build Adjacency Representations, watch for students assuming matrices always outperform lists because they are more familiar.

  Have pairs calculate the actual memory used by both representations for their specific graph and present their findings to the class to confront the assumption directly.

• During Small Groups: Token Traversal Simulation, watch for students thinking BFS and DFS produce the same node order in all graphs.

  Ask groups to swap graphs and repeat the simulation, then compare orders side by side during a class debrief to highlight structural dependence.

• During Whole Class: Pathfinding Challenge, watch for students limiting graphs to spatial networks like roads or maps.

  Prompt teams to adapt their traversals to non-spatial examples like social network friendships or course prerequisites, and present how the same algorithm applies.

---

Methods used in this brief

• Concept Mapping