Computer Science · 12th Grade · Object-Oriented Design and Data Structures · Weeks 10-18

Graphs: Representation and Basic Properties

Students learn different ways to represent graphs (adjacency matrix, adjacency list) and understand basic graph properties.

• Common Core State Standards
• CSTA: 3B-AP-12
• CSTA: 3B-AP-14

About This Topic

Graphs extend the data structures toolkit to model relationships that trees and arrays cannot represent: road networks, social connections, dependency chains, and internet topology all map naturally to graphs. In US 12th-grade CS, students learn to distinguish directed from undirected graphs, weighted from unweighted edges, and sparse from dense graphs, distinctions that directly determine which representation to choose.

Two representations dominate in practice. An adjacency matrix uses a 2D array where entry [i][j] indicates an edge between vertices i and j. It supports O(1) edge lookup and is straightforward to implement, but consumes O(V²) space regardless of how many edges actually exist, wasteful for sparse graphs. An adjacency list stores only the edges that exist, using an array of lists indexed by vertex. Space drops to O(V + E), and iteration over a vertex's neighbors becomes proportional to the actual degree rather than the total vertex count.

Active learning is particularly effective for graphs because students can build physical or whiteboard representations of the same real-world network in both formats and directly compare the resulting trade-offs rather than reasoning about them abstractly.

Key Questions

1. Compare adjacency matrix and adjacency list representations for different graph types.
2. Analyze how the choice of graph representation impacts algorithm efficiency.
3. Construct a graph representation for a real-world network problem.

Learning Objectives

• Compare the space and time complexity of adjacency matrix versus adjacency list representations for graph operations.
• Analyze the trade-offs between adjacency matrix and adjacency list representations for sparse and dense graphs.
• Construct an appropriate graph representation (adjacency matrix or list) for a given real-world network problem.
• Evaluate the impact of graph representation choice on the efficiency of common graph algorithms, such as searching or traversal.

Before You Start

Arrays and Lists

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

Basic Algorithm Analysis (Big O Notation)

Why: Understanding Big O notation is crucial for analyzing the time and space complexity trade-offs between different graph representations.

Key Vocabulary

Graph	A data structure consisting of a set of vertices (nodes) and a set of edges connecting pairs of vertices.
Adjacency Matrix	A square matrix used to represent a finite graph where the element at row i and column j indicates if there is an edge between vertex i and vertex j.
Adjacency List	A collection of lists, where each list stores the neighbors of a particular vertex in the graph.
Vertex	A fundamental unit of a graph, often represented as a point or a node.
Edge	A connection between two vertices in a graph, representing a relationship or link.

Watch Out for These Misconceptions

Common Misconception

Adjacency matrices are always wasteful because they use O(V²) space.

What to Teach Instead

For dense graphs, where most possible edges exist, an adjacency matrix is space-efficient because the O(V²) slots are mostly filled. The wastefulness only appears in sparse graphs. Having students calculate actual space usage for both representations on a concrete example makes the density argument clear.

Common Misconception

Trees are a completely separate concept from graphs.

What to Teach Instead

A tree is a specific type of graph: connected, undirected, and acyclic with exactly V-1 edges. Recognizing trees as a restricted case of graphs helps students apply graph algorithms to tree problems and understand why tree algorithms cannot always extend to general graphs.

Common Misconception

The adjacency list is always better than the adjacency matrix because it uses less memory.

What to Teach Instead

Memory advantage depends on graph density. Adjacency lists also involve pointer overhead and non-contiguous memory access, which can be slower for cache performance. For dense graphs, the matrix's contiguous memory layout may actually give better practical performance despite higher theoretical space usage.

Active Learning Ideas

Think-Pair-Share: Which Representation Fits?

Present three scenarios: a flight network with thousands of airports and thousands of routes, a small friend network of eight people all connected to each other, and a dependency graph for a build system with hundreds of files. Pairs decide which representation fits each scenario and calculate space requirements. Sharing out surfaces the density argument clearly.

15 min·Pairs

Collaborative Problem-Solving: Build a Graph from Real Data

Students download a small public dataset, such as US city driving distances or a Wikipedia link sample, and implement both an adjacency matrix and an adjacency list in Python. They then write a function to count a given vertex's neighbors and compare how long each representation takes. Comparing runtime and memory usage grounds the theory in observable results.

45 min·Pairs

Gallery Walk: Graph Property Identification

Post six graph diagrams around the room (directed, undirected, weighted, cyclic, disconnected, bipartite). Groups rotate every three minutes and annotate each graph with its properties. The debrief asks groups to justify their classifications and identify which properties affect algorithm choice.

20 min·Small Groups

Jigsaw: Graph Representation Trade-offs

Divide the class into matrix experts and list experts. Each group studies the space complexity, edge-lookup time, and neighbor-iteration time for their representation using a provided reference. Groups then regroup with one member from each side and teach each other, producing a combined comparison table to share with the class.

30 min·Small Groups

Real-World Connections

• Social media platforms like Facebook or LinkedIn use graph structures to represent user connections. Choosing between adjacency lists and matrices impacts how quickly friend suggestions can be generated or how many mutual friends are found.
• Mapping services such as Google Maps or Waze model road networks as graphs. The representation chosen affects the speed and memory usage when calculating the shortest route between two locations, especially in large, complex city grids.
• Computer network topology, like the internet backbone, can be modeled as a graph. Network engineers consider graph representations to efficiently route data packets and identify potential bottlenecks or points of failure.

Assessment Ideas

Exit Ticket

Provide students with two scenarios: a social network with 1000 users and 5000 connections, and a grid of 100 sensors with each sensor connected to its four immediate neighbors. Ask students to identify the most suitable graph representation for each scenario and briefly justify their choice, considering space efficiency.

Quick Check

Present a small graph (5-7 vertices) on the board. Ask students to individually draw both the adjacency matrix and the adjacency list for this graph. Then, ask them to identify the time complexity for checking if an edge exists between two specific vertices for each representation.

Discussion Prompt

Facilitate a class discussion using the prompt: 'Imagine you are designing a system to track flight paths between major airports. What are the advantages and disadvantages of using an adjacency matrix versus an adjacency list for this problem? How might the number of flights (edges) compared to the number of airports (vertices) influence your decision?'

Frequently Asked Questions

What is the difference between an adjacency matrix and an adjacency list?

An adjacency matrix is a 2D array where cell [i][j] equals 1 if an edge exists between vertices i and j. An adjacency list stores each vertex's neighbors in a separate list. Matrices offer O(1) edge lookup but use O(V²) space. Lists use O(V+E) space and are faster for iterating over a vertex's neighbors in sparse graphs.

When should I use an adjacency matrix versus an adjacency list?

Use an adjacency matrix when the graph is dense (many edges relative to vertices), when O(1) edge-existence checks are critical, or when the graph is small enough that space is not a concern. Use an adjacency list when the graph is sparse, when you frequently need to iterate over a vertex's neighbors, or when memory efficiency matters.

What makes a graph directed versus undirected?

A directed graph (digraph) has edges with a specific direction, an edge from A to B does not imply an edge from B to A. An undirected graph treats edges as bidirectional. Social media follower relationships are directed; friendship relationships are undirected. This distinction affects how algorithms like shortest path and cycle detection are implemented.

How does active learning help students understand graph representations?

Building both representations for the same real-world network, like a classroom friendship graph or a city road map, makes the space and time trade-offs visible and personally meaningful. Students who construct the matrix and list by hand and then measure lookup times develop a durable intuition that is harder to gain from reading about the representations in a textbook.