Computer Science · Grade 12 · Data Structures and Abstract Data Types · Term 1

Graphs: Representation and Traversal

Introduction to graph data structures, their representations (adjacency matrix/list), and basic traversal algorithms (BFS/DFS).

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

About This Topic

Graphs represent relationships between entities, such as cities connected by roads or friends in a social network. Grade 12 students explore adjacency matrices, which use a 2D array to show direct connections, and adjacency lists, which store neighbors in linked structures for efficiency with sparse graphs. They implement basic traversals: Breadth-First Search (BFS) using queues to explore level by level, and Depth-First Search (DFS) with stacks or recursion to probe deeply before backtracking. These tools address key questions like comparing representations and detecting paths between nodes.

This topic aligns with Ontario's CS.DSAA.12 and CS.P.12 standards by developing skills in abstract data types, algorithmic design, and time complexity analysis. Students analyze when matrices suit dense graphs versus lists for sparse ones, and how BFS finds shortest paths while DFS suits cycle detection. Real-world applications include GPS routing and web page crawling, fostering problem-solving for complex systems.

Active learning suits graphs because students can draw networks on paper, simulate traversals with tokens, and code iteratively in pairs. These hands-on methods clarify abstract concepts, reveal traversal differences visually, and build confidence through peer debugging.

Key Questions

1. Compare adjacency matrix and adjacency list representations for graphs.
2. Explain the differences between Breadth-First Search (BFS) and Depth-First Search (DFS).
3. Design an algorithm to find if a path exists between two nodes in a graph.

Learning Objectives

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

Before You Start

Arrays and Linked Lists

Why: Students need a solid understanding of these fundamental data structures to grasp how adjacency matrices and adjacency lists are implemented.

Queues and Stacks

Why: BFS relies on queues and DFS typically uses stacks (or recursion, which implies stack usage), making prior knowledge of these abstract data types essential.

Basic Algorithmic Concepts

Why: Students should be familiar with concepts like loops, conditional statements, and function calls to understand and implement traversal algorithms.

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.

Watch Out for These Misconceptions

Common Misconception

Adjacency matrices are always more efficient than lists.

What to Teach Instead

Matrices use O(V^2) space regardless of edges, wasting memory on sparse graphs, while lists use O(V+E). Pairs activities building both reveal this through manual counting, and coding space checks solidify efficiency analysis.

Common Misconception

BFS and DFS always visit nodes in the same order.

What to Teach Instead

Order depends on neighbor listing and structure; BFS is level-order, DFS branch-order. Token simulations in groups highlight differences visually, with peer comparisons correcting assumptions during discussions.

Common Misconception

Graphs only model physical connections like roads.

What to Teach Instead

Graphs model any pairwise relations, from web links to dependencies. Real-world mapping activities expand this view, as students adapt traversals to non-spatial examples like prerequisite courses.

Active Learning Ideas

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.

30 min·Pairs

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.

45 min·Small Groups

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.

20 min·Whole Class

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.

25 min·Individual

Real-World Connections

• Social networks like Facebook use graph structures to represent friendships and connections. Algorithms like BFS can find the shortest path (fewest connections) between two users, a concept known as 'degrees of separation'.
• Mapping services such as Google Maps or Waze employ graph algorithms to find the shortest or fastest routes between locations. BFS can be used to find the minimum number of transfers needed for public transit, while DFS might be used in more complex route optimization scenarios.
• Computer network engineers use graph theory to model network topology and design efficient data routing protocols. They analyze connectivity and potential bottlenecks using traversal algorithms to ensure reliable communication.

Assessment Ideas

Quick Check

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.

Exit Ticket

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.

Discussion Prompt

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?'

Frequently Asked Questions

How do adjacency matrices and lists compare for graph representation?

Matrices store connections in a VxV grid: simple O(1) edge checks but high space for sparse graphs. Lists chain neighbors per vertex: efficient O(deg(v)) checks and O(V+E) space. Hands-on coding both on sample graphs lets students measure differences, connecting to Big O analysis in curriculum standards.

What are the key differences between BFS and DFS traversals?

BFS uses a queue for level-by-level exploration, ideal for shortest paths in unweighted graphs. DFS uses a stack or recursion for deep dives, better for connectivity or cycles. Simulations with tokens clarify these, as students see BFS spread wide first versus DFS tunnel deep, matching key curriculum questions.

How can active learning help teach graph traversals?

Active methods like token simulations and pair coding make traversals tangible: students physically move markers on graphs to mimic queues/stacks, predict orders, and debug paths collaboratively. This reveals why BFS finds shortest paths while DFS backtracks, building intuition over rote memorization. Class discussions refine understanding through shared predictions.

What real-world problems use graph traversal algorithms?

BFS powers GPS shortest routes and social network degrees-of-separation. DFS aids maze solving, deadlock detection in OS, and web crawlers. Students design pathfinding algorithms for these, applying representations to optimize, which ties abstract CS to practical Ontario curriculum expectations like CS.P.12.