Computer Science · 11th Grade · Algorithmic Thinking and Complexity · Weeks 1-9

Introduction to Data Structures: Graphs

Basic concepts of graphs as a data structure and their real-world applications.

• Common Core State Standards
• CSTA: 3B-AP-13

About This Topic

Graphs are one of the most versatile data structures in computer science, capable of modeling anything from social networks and road maps to dependencies between software packages and relationships between web pages. This topic introduces CSTA standard 3B-AP-13 and gives 11th-grade students their first formal vocabulary for thinking about connected data: nodes, edges, directed versus undirected graphs, and weighted versus unweighted graphs.

In the US K-12 curriculum, graphs are often students' first encounter with a data structure that has no obvious physical analogy. Lists and arrays feel like rows of boxes; graphs feel abstract. Grounding the introduction in familiar networks (friend connections on social media, roads between cities, flight routes between airports) helps students build the mental model they need before moving to implementation. This topic also sets up later work on graph traversal algorithms like BFS and DFS.

Active learning is productive here because the structure of graphs is naturally visual and collaborative. Building physical graph models with string and cards, or mapping classroom social connections as a graph, gives students a tactile experience of the data structure before they encounter formal definitions.

Key Questions

1. Explain what a graph is and identify its components (nodes/vertices, edges).
2. Analyze real-world examples that can be modeled using graphs (e.g., social networks, road maps).
3. Differentiate between various ways to represent a graph (e.g., drawing, adjacency list concept).

Learning Objectives

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

Before You Start

Introduction to Data Types and Variables

Why: Students need a basic understanding of how data is stored and represented to grasp the concept of nodes and edges as data elements.

Basic Algorithmic Thinking

Why: Familiarity with sequential steps and logical operations is helpful for understanding how relationships between data points are processed.

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.

Watch Out for These Misconceptions

Common Misconception

Graphs and trees are the same thing.

What to Teach Instead

Trees are a special case of graphs with no cycles and a defined root, but most graphs are neither. Many students conflate the two because trees appear earlier in the curriculum. A bidirectional road map between cities with multiple paths quickly demonstrates the distinction.

Common Misconception

All graphs must have edges between every pair of nodes.

What to Teach Instead

Sparse graphs where most nodes have only a few connections are extremely common. Social networks have billions of users but each person connects to only a tiny fraction of them. Activities analyzing real network data help students see that sparsity is normal, not a special case.

Common Misconception

Graph edges must be symmetric (if A connects to B, B connects to A).

What to Teach Instead

Directed graphs explicitly model one-way relationships like web links, Instagram follows, or one-way streets. Students often assume reciprocity by default. Using concrete directed examples early in instruction prevents this assumption from hardening into a misconception.

Active Learning Ideas

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.

20 min·Whole Class

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.

15 min·Pairs

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.

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

25 min·Small Groups

Real-World Connections

• Social media platforms like Facebook or Instagram use graphs to model friendships and connections between users, allowing for features like friend suggestions and content recommendations.
• Mapping applications such as Google Maps or Waze represent road networks as graphs, where intersections are nodes and roads are edges, enabling efficient route calculation and traffic analysis.
• Airline route planners utilize graphs to map flight paths between cities, with cities as nodes and flights as directed edges, helping to optimize schedules and manage passenger flow.

Assessment Ideas

Exit Ticket

Provide students with a scenario, such as 'a city bus system'. Ask them to draw a small graph representing a few bus stops and routes. They should label the nodes and edges and indicate if the graph is directed or undirected, explaining their choices.

Discussion Prompt

Present students with two different real-world examples: a family tree and a subway map. Ask: 'How are these similar in terms of their underlying structure? How are they different? What kind of graph representation (directed/undirected, weighted/unweighted) would best model each, and why?'

Quick Check

Show students a visual representation of a graph (e.g., a simple drawing with dots and lines). Ask them to count and state the number of nodes and edges. Then, present a second graph and ask if it represents a directed or undirected relationship, and why.

Frequently Asked Questions

What is a graph data structure in computer science?

A graph is a collection of nodes (also called vertices) connected by edges. Unlike trees or lists, graphs can have cycles, disconnected components, and edges that carry weights or directions. They are used to model any system where items have relationships with other items, such as social networks, road maps, or computer networks.

What is the difference between a directed and undirected graph?

In an undirected graph, edges have no direction (friendship on Facebook is mutual). In a directed graph, edges point from one node to another and the relationship may not be reciprocal (Instagram follows, one-way streets). Choosing the right type depends on whether the relationships in your data are symmetric or asymmetric.

How are graphs used in real computer science applications?

Graph algorithms power GPS routing (shortest path), social network analysis (friend recommendations), web search (PageRank), dependency resolution (package managers), and task scheduling. Most large-scale software systems use some form of graph processing, making this one of the most practically important data structures students will encounter.

What active learning approaches work best for teaching graph data structures?

Physical construction activities where students act as nodes and form edges with yarn give concrete, memorable experience with graph properties before formal definitions. Analyzing real-world network data in small groups then presents the data structure in meaningful context, which research shows improves retention and transfer compared to abstract examples alone.