Computer Science · 12th Grade

Active learning ideas

Graphs: Representation and Basic Properties

Active learning works for graphs because students need to wrestle with real trade-offs to internalize why representation matters. Static definitions don’t stick when the choice between adjacency list and matrix changes from wasteful to wise depending on graph density.

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

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

Activity 01

• Think-Pair-Share
• 15 min · Pairs

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.

Compare adjacency matrix and adjacency list representations for different graph types.

Facilitation Tip

During the Think-Pair-Share, circulate and listen for students to name the exact graph property that justifies their representation choice, not just guessing.

What to look for

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.

• Understand
• Apply
• Analyze
• Self-Awareness
• Relationship Skills

Activity 02

• Collaborative Problem-Solving
• 45 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.

Analyze how the choice of graph representation impacts algorithm efficiency.

Facilitation Tip

In the Lab, provide real datasets in CSV format so students practice cleaning and mapping data to graph edges before building code.

What to look for

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.

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

Activity 03

• Gallery Walk
• 20 min · Small Groups

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.

Construct a graph representation for a real-world network problem.

Facilitation Tip

For the Gallery Walk, assign small groups to critique one property poster using a provided rubric, ensuring accountability for thoughtful feedback.

What to look for

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

• Understand
• Apply
• Analyze
• Create
• Relationship Skills
• Social Awareness

Activity 04

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

Compare adjacency matrix and adjacency list representations for different graph types.

Facilitation Tip

During the Jigsaw, ask each expert group to prepare a one-slide summary with a concrete density calculation to present back to their home group.

What to look for

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.

• Understand
• Analyze
• Evaluate
• Relationship Skills
• Self-Management

A few notes on teaching this unit

Approach this topic by letting students experience the pain of poor choices firsthand. Have them implement both representations for the same graph and time edge-lookup operations, then debrief on why cache locality and memory layout matter in practice. Avoid lecturing on big-O until students feel its impact through concrete measurements. Research shows that students grasp asymptotic reasoning better when it emerges from real data rather than abstract formulas.

Successful learning looks like students confidently choosing representations based on concrete properties such as density, edge count, and access patterns. They should articulate why one representation wins over another in a given scenario.

---

Watch Out for These Misconceptions

• During the Think-Pair-Share activity, watch for students who claim adjacency matrices are always wasteful because they use O(V²) space.

  Ask these students to calculate the actual space used by both representations for their chosen graph in the Think-Pair-Share handout. Have them count edges and compare the ratio of filled slots to total slots to reveal when a matrix is efficient.

• During the Gallery Walk activity, watch for students who treat trees as completely separate from graphs.

  Have students examine the Gallery Walk posters for tree examples and ask them to verify the three defining properties: connected, acyclic, V-1 edges. Prompt them to redraw the tree as a graph and label which properties hold.

• During the Jigsaw activity, watch for students who insist adjacency lists are always better because they use less memory.

  Ask these students to consult the Jigsaw handout with density calculations. Have them compare pointer overhead and cache performance for dense graphs and report back to their group with evidence.

---

Methods used in this brief

• Think-Pair-Share
• Collaborative Problem-Solving
• Gallery Walk
• Jigsaw