Introduction to Data Structures: Graphs

Graphs are abstract and visual, which makes them perfect for active learning. Students need to physically and socially engage with nodes, edges, and relationships to move beyond memorizing vocabulary and start recognizing graphs in their daily lives.

• 11th Grade
• Computer Science
• 4 activities
• 15 min–30 min

Learning Objectives

1. Identify the components of a graph, including nodes (vertices) and edges.
2. Analyze real-world scenarios and classify them as potential graph models.
3. Compare and contrast different methods for representing a graph, such as visual drawings and adjacency lists.
4. Explain the difference between directed and undirected graphs, and weighted and unweighted graphs.

Concept Mapping

⏱ 20 min·Whole Class

Kinesthetic Activity: Human Graph Construction

Students each represent a node and use yarn or string to form edges based on relationships (who lives nearest, who shares a hobby). The class then analyzes properties: Is the graph directed or undirected? Weighted? Does everyone have a path to everyone else? This creates immediate intuition for graph vocabulary before formal definitions.

Prepare & details

Explain what a graph is and identify its components (nodes/vertices, edges).

Facilitation Tip: During Human Graph Construction, assign roles like timekeeper and recorder to keep movement organized and purposeful.

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

Think-Pair-Share

⏱ 15 min·Pairs

Think-Pair-Share: Real-World Graph Identification

Students receive a list of 8 real-world systems (airline routes, power grids, Facebook friendships, course prerequisites) and individually identify which are best modeled as directed versus undirected graphs and why. Pairs compare and defend their reasoning before a class discussion surfaces interesting edge cases.

Prepare & details

Analyze real-world examples that can be modeled using graphs (e.g., social networks, road maps).

Facilitation Tip: For Real-World Graph Identification, provide a mix of obvious and subtle examples to push students beyond surface-level connections.

Setup: Standard classroom seating; students turn to a neighbor

Materials: Discussion prompt (projected or printed), Optional: recording sheet for pairs

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

Gallery Walk

⏱ 30 min·Small Groups

Gallery Walk: Graph Representation Comparison

Groups create side-by-side posters showing the same small graph as a drawing and as an adjacency list. Other groups annotate which representation they would prefer for different operations (adding a node, finding all neighbors) and leave sticky-note reasoning on each poster.

Prepare & details

Differentiate between various ways to represent a graph (e.g., drawing, adjacency list concept).

Facilitation Tip: In Gallery Walk, require each group to present one representation they found most challenging to interpret.

Setup: Wall space or tables arranged around room perimeter

Materials: Large paper/poster boards, Markers, Sticky notes for feedback

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

Case Study Analysis

⏱ 25 min·Small Groups

Case Study Analysis: The Internet as a Graph

Groups analyze a simplified diagram of internet router connections and answer structured questions: How many hops does it take to travel from node A to node B? What happens if one node fails? What does edge weight represent here? Groups share findings and connect to real network design decisions.

Prepare & details

Explain what a graph is and identify its components (nodes/vertices, edges).

Facilitation Tip: During The Internet as a Case Study, provide a simplified URL network so students can trace paths without feeling overwhelmed by scale.

Setup: Groups at tables with case materials

Materials: Case study packet (3-5 pages), Analysis framework worksheet, Presentation template

• Analyze
• Evaluate
• Create
• Decision-Making
• Self-Management

Teaching This Topic

Start with concrete, relatable examples before introducing formal definitions. Avoid overwhelming students with too many graph types at once. Use analogies carefully, as they can reinforce misconceptions if not precise. Research shows that students grasp abstract structures better when they first experience them through physical movement and social interaction.

What to Expect

Students will confidently identify and describe graphs using correct terminology, explain differences between graph types, and apply these concepts to real-world scenarios with clear reasoning.

Watch Out for These Misconceptions

Common Misconception

During Human Graph Construction, watch for students who equate all graphs with trees because they see the connecting lines as hierarchical.

What to Teach Instead

After students build their human graph, ask them to identify any cycles or multiple paths between nodes. Then, have them modify their graph to remove cycles and designate a root to see how it changes into a tree structure.

Common Misconception

During Real-World Graph Identification, watch for students who assume every graph must have many connections between nodes.

What to Teach Instead

When analyzing sparse examples like a subway map, have students count the average connections per node and compare it to a family tree example to highlight the difference between dense and sparse graphs.

Common Misconception

During Gallery Walk, watch for students who assume all edges represent two-way relationships.

What to Teach Instead

At each station, ask students to check whether reversing an edge would make sense in the real-world context. For directed examples like web links, have them physically turn their bodies to demonstrate one-way relationships.

Assessment Ideas

Exit Ticket

After Human Graph Construction, ask students to draw a small graph based on the human network they created, labeling nodes, edges, and graph type (directed/undirected, weighted/unweighted).

Discussion Prompt

During Real-World Graph Identification, ask students to compare a family tree and a bus route map. Have them explain which graph type fits each and why, focusing on differences in edge directionality and structure.

Quick Check

After Gallery Walk, show a visual graph and ask students to identify the number of nodes and edges, then determine if it is directed or undirected based on the context provided.

Extensions & Scaffolding

• Challenge: Ask students to design a graph representing their school’s social dynamics (e.g., friendships, clubs) and present it with a short explanation of what their design choices reveal.
• Scaffolding: Provide pre-labeled node and edge templates for students to arrange during Human Graph Construction if they struggle with abstraction.
• Deeper exploration: Introduce the concept of graph density and have students calculate and compare densities of different real-world networks they’ve identified.

Key Vocabulary

Node (Vertex)	A fundamental unit in a graph, representing an object or entity. Think of it as a point or a location.
Edge	A connection between two nodes, representing a relationship or pathway between them. It's the line that links the points.
Directed Graph	A graph where edges have a specific direction, indicating a one-way relationship from one node to another.
Undirected Graph	A graph where edges do not have a direction, indicating a two-way relationship between connected nodes.
Weighted Graph	A graph where edges have an associated numerical value, often representing cost, distance, or capacity.