Graphs: Representation and Basic PropertiesActivities & Teaching Strategies
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.
Learning Objectives
- 1Compare the space and time complexity of adjacency matrix versus adjacency list representations for graph operations.
- 2Analyze the trade-offs between adjacency matrix and adjacency list representations for sparse and dense graphs.
- 3Construct an appropriate graph representation (adjacency matrix or list) for a given real-world network problem.
- 4Evaluate the impact of graph representation choice on the efficiency of common graph algorithms, such as searching or traversal.
Want a complete lesson plan with these objectives? Generate a Mission →
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.
Prepare & details
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.
Setup: Standard classroom seating; students turn to a neighbor
Materials: Discussion prompt (projected or printed), Optional: recording sheet for 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.
Prepare & details
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.
Setup: Groups at tables with problem materials
Materials: Problem packet, Role cards (facilitator, recorder, timekeeper, reporter), Problem-solving protocol sheet, Solution evaluation rubric
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.
Prepare & details
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.
Setup: Wall space or tables arranged around room perimeter
Materials: Large paper/poster boards, Markers, Sticky notes for feedback
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.
Prepare & details
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.
Setup: Flexible seating for regrouping
Materials: Expert group reading packets, Note-taking template, Summary graphic organizer
Teaching This Topic
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.
What to Expect
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.
These activities are a starting point. A full mission is the experience.
- Complete facilitation script with teacher dialogue
- Printable student materials, ready for class
- Differentiation strategies for every learner
Watch Out for These Misconceptions
Common MisconceptionDuring the Think-Pair-Share activity, watch for students who claim adjacency matrices are always wasteful because they use O(V²) space.
What to Teach Instead
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.
Common MisconceptionDuring the Gallery Walk activity, watch for students who treat trees as completely separate from graphs.
What to Teach Instead
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.
Common MisconceptionDuring the Jigsaw activity, watch for students who insist adjacency lists are always better because they use less memory.
What to Teach Instead
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.
Assessment Ideas
After the Lab, distribute an exit ticket with two scenarios: a social network with 1000 users and 5000 connections, and a grid of 100 sensors with each connected to four neighbors. Ask students to identify the most suitable representation for each and justify their choice in one sentence using space efficiency.
During the Think-Pair-Share, present a small graph on the board and ask students to individually sketch both the adjacency matrix and adjacency list. Then, ask them to write the time complexity for checking if an edge exists between two specific vertices for each representation on their mini whiteboards.
After the Jigsaw, facilitate a whole-class discussion using the prompt: ‘Airport designers choose between adjacency matrix and list. What are the advantages and disadvantages of each? How might the number of flights compared to airports influence the decision?’ Use the Jigsaw posters as visual references during the discussion.
Extensions & Scaffolding
- Challenge: Ask students to extend their graph from the Lab to include weights and then implement Dijkstra’s algorithm, noting how the chosen representation affects performance.
- Scaffolding: Provide a partially completed adjacency matrix template so students can focus on converting sparse data into filled slots without worrying about formatting.
- Deeper exploration: Invite students to research and present on how graph databases like Neo4j store data internally and how that design influences query speed for social network features.
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. |
Suggested Methodologies
More in Object-Oriented Design and Data Structures
OOP Principles: Encapsulation and Abstraction
Students explore the core OOP principles of encapsulation and abstraction, understanding how they promote modularity and data hiding.
2 methodologies
Inheritance and Polymorphism in Depth
Students design class hierarchies that promote code reuse and flexibility, implementing interfaces and abstract classes.
2 methodologies
Introduction to Generic Programming
Students learn to write generic classes and methods that can operate on different data types, enhancing code reusability.
2 methodologies
Implementing Linked Lists (Singly and Doubly)
Students build and manipulate singly and doubly linked lists from scratch, understanding dynamic memory allocation.
2 methodologies
Stacks: LIFO Data Structure
Students implement stack data structures and explore their applications in function call management and expression evaluation.
2 methodologies
Ready to teach Graphs: Representation and Basic Properties?
Generate a full mission with everything you need
Generate a Mission