Introduction to Graph Algorithms

Active learning works for graph algorithms because these concepts are inherently visual and kinesthetic. Moving from abstract diagrams to human-scale simulations helps students internalize how traversals work. By physically acting out BFS and DFS, tracing paths on paper, and debating algorithm choices, students build durable mental models instead of memorizing steps.

• 10th Grade
• Computer Science
• 4 activities
• 25 min–40 min

Learning Objectives

1. Identify the components of a graph, including vertices and edges, from a given diagram or description.
2. Explain the step-by-step process of Breadth-First Search (BFS) traversal on a provided graph.
3. Predict the sequence of visited nodes when applying Depth-First Search (DFS) starting from a specified node in a graph.
4. Compare the traversal paths generated by BFS and DFS on the same graph, highlighting key differences in exploration strategy.

Role Play

⏱ 25 min·Whole Class

Role Play: Human BFS and DFS

Students each receive a node number. For BFS, the teacher calls out nodes by layer: start node, then all its neighbors, then all their unvisited neighbors. For DFS, one path is followed as deep as possible before backtracking. Students stand when visited. The contrast in visiting order between BFS and DFS is immediate and memorable with 10-15 students.

Prepare & details

Explain the components of a graph and their representation.

Facilitation Tip: During Human BFS and DFS, assign clear roles for 'explorers', 'queue trackers', and 'visited node markers' to avoid chaos and keep everyone engaged.

Setup: Open space or rearranged desks for scenario staging

Materials: Character cards with backstory and goals, Scenario briefing sheet

• Apply
• Analyze
• Evaluate
• Social Awareness
• Self-Awareness

Inquiry Circle

⏱ 35 min·Small Groups

Inquiry Circle: Trace the Traversal

Groups of 3 receive a drawn graph with 7-8 nodes and perform both BFS and DFS starting from the same node, writing out the order of visited nodes for each. Groups compare their BFS and DFS orderings and explain why they differ. Surfaces that the same graph yields different valid orderings and that algorithm choice determines what you find first.

Prepare & details

Analyze the process of Breadth-First Search (BFS) on a given graph.

Facilitation Tip: During Trace the Traversal, have students work in pairs so one student traces with a colored pen while the other records the step-by-step order aloud.

Setup: Groups at tables with access to source materials

Materials: Source material collection, Inquiry cycle worksheet, Question generation protocol, Findings presentation template

• Analyze
• Evaluate
• Create
• Self-Management
• Self-Awareness

Think-Pair-Share

⏱ 25 min·Pairs

Think-Pair-Share: Which Search Fits the Problem?

Present four real-world scenarios: finding the shortest path in a road network, checking if two users are connected in a social network, exploring all files reachable from a root directory, and detecting circular dependencies in software packages. Pairs match each to BFS or DFS and justify the choice, then share reasoning with the class.

Prepare & details

Predict the path taken by Depth-First Search (DFS) from a starting node.

Facilitation Tip: During Which Search Fits the Problem?, circulate and listen for students using terms like 'shortest path' or 'depth-first exploration' to describe their reasoning.

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

⏱ 40 min·Small Groups

Gallery Walk: Graph Representation Challenge

Post four graphs around the room, each shown in one format: adjacency matrix, adjacency list, edge list, or visual diagram. Students must create the other three representations for each graph they visit. Reinforces that the same graph has multiple valid representations and that algorithm implementation depends on knowing which to use.

Prepare & details

Explain the components of a graph and their representation.

Facilitation Tip: During Graph Representation Challenge, provide blank grids and ask students to convert between visual diagrams and adjacency lists before moving to code.

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

Teaching This Topic

Experienced teachers approach graph algorithms by balancing concrete experience with abstract generalization. Start with physical simulations to build intuition, then transition to paper-and-pencil tracing to internalize the rules. Emphasize the difference between linear structures and relational ones by repeatedly asking students to explain why visited tracking matters. Avoid rushing to code; students need to feel the algorithms in their bodies before they can debug them on a computer.

What to Expect

Successful learning looks like students explaining why BFS visits nodes by distance while DFS follows a single path, identifying which algorithm fits a given problem, and representing graphs accurately using both adjacency lists and matrices. Students should also justify their choices with clear graph terminology.

Watch Out for These Misconceptions

Common Misconception

During Human BFS and DFS, watch for students believing BFS and DFS visit nodes in the same order.

What to Teach Instead

Use the human simulation to physically mark nodes with distance labels for BFS (like breadcrumbs) and show how DFS follows one path deep before backtracking, making the order difference visible.

Common Misconception

During Graph Representation Challenge, watch for students treating graphs as linear structures like lists or arrays.

What to Teach Instead

Have students compare their adjacency lists to their visual diagrams, pointing out cycles and multiple connections that lists cannot represent linearly.

Assessment Ideas

Quick Check

After Human BFS and DFS, provide a small labeled graph and ask students to draw the visit order for BFS and DFS from a given start node, checking for correct application of each algorithm's rules.

Exit Ticket

During Graph Representation Challenge, collect students' adjacency lists or matrices and ask them to define 'vertex' and 'edge' in their own words on the back, then describe one scenario where BFS or DFS would be more appropriate.

Discussion Prompt

After Which Search Fits the Problem?, pose the question: 'Imagine designing a game where players explore a dungeon. Which traversal algorithm is better for finding all hidden treasures, and why?' Listen for graph terminology in their explanations.

Extensions & Scaffolding

• Challenge early finishers to design a graph where BFS and DFS visit nodes in exactly the same order, then justify why this is possible or impossible.
• Scaffolding for struggling students: Provide a partially completed adjacency matrix or list and ask them to finish it before tracing traversals.
• Deeper exploration: Introduce weighted graphs and ask students to compare BFS and DFS on a small graph with varying edge weights.

Key Vocabulary

Vertex (Node)	A fundamental unit in a graph, representing an object or point. Multiple vertices are connected by edges.
Edge	A connection between two vertices in a graph. Edges can be directed or undirected, representing relationships or links.
Graph Traversal	The process of visiting each vertex in a graph systematically. Algorithms like BFS and DFS are common traversal methods.
Breadth-First Search (BFS)	A graph traversal algorithm that explores neighbor nodes first before moving to the next level neighbors. It is often used to find the shortest path in an unweighted graph.
Depth-First Search (DFS)	A graph traversal algorithm that explores as far as possible along each branch before backtracking. It is useful for finding cycles or exploring all reachable nodes.