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.

• Grade 12
• Computer Science
• 4 activities
• 20 min–45 min

Learning Objectives

1. Compare the space and time complexity trade-offs between adjacency matrix and adjacency list graph representations.
2. Explain the algorithmic steps of Breadth-First Search (BFS) and Depth-First Search (DFS) for graph traversal.
3. Design an algorithm using BFS or DFS to determine if a path exists between two specified nodes in a graph.
4. Analyze the suitability of BFS versus DFS for specific graph problems, such as finding the shortest path or detecting cycles.

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.

Prepare & details

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.

Setup: Tables with large paper, or wall space

Materials: Concept cards or sticky notes, Large paper, Markers, Example concept map

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

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.

Prepare & details

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.

Setup: Tables with large paper, or wall space

Materials: Concept cards or sticky notes, Large paper, Markers, Example concept map

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

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.

Prepare & details

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.

Setup: Tables with large paper, or wall space

Materials: Concept cards or sticky notes, Large paper, Markers, Example concept map

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

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.

Prepare & details

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.

Setup: Tables with large paper, or wall space

Materials: Concept cards or sticky notes, Large paper, Markers, Example concept map

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

Teaching This Topic

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.

What to Expect

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

Common Misconception

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

What to Teach Instead

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.

Common Misconception

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

What to Teach Instead

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

Common Misconception

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

What to Teach Instead

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

Assessment Ideas

Quick Check

After Pairs Coding, present students with a small graph on the board and ask them to vote with fingers (1 for matrix, 2 for list) and justify their choice aloud using the memory counts they calculated during the activity.

Exit Ticket

After Small Groups: Token Traversal Simulation, provide a simple graph and two nodes, A and B, and ask students to write the BFS and DFS sequences starting from A, noting whether they used a stack or recursion for DFS.

Discussion Prompt

During Whole Class: Pathfinding Challenge, ask teams to debate which traversal they would choose to ensure every page on a website is reachable from the homepage, then share their reasoning and potential pitfalls of the alternative algorithm in a whole-class discussion.

Extensions & Scaffolding

• Challenge early finishers to implement bidirectional BFS and explain how it reduces the search space in sparse graphs.
• Scaffolding for struggling students: provide partially filled adjacency lists with hints about edge directions, and give a pre-written DFS stack to trace.
• Deeper exploration: invite students to research how Dijkstra’s algorithm adapts BFS for weighted graphs, then modify their BFS code to handle weights.

Key Vocabulary

Graph	A data structure consisting of a set of nodes (vertices) and a set of edges connecting pairs of nodes, representing relationships between entities.
Adjacency Matrix	A 2D array used to represent a graph, where the value at matrix[i][j] indicates an edge between node i and node j. It is efficient for dense graphs.
Adjacency List	A collection of lists, where each list stores the neighbors of a particular node. It is efficient for sparse graphs.
Breadth-First Search (BFS)	A graph traversal algorithm that explores nodes level by level, starting from a source node, 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.