Computer Science · 12th Grade

Active learning ideas

Graph Traversal Algorithms: BFS and DFS

Active learning works for graph traversal because these algorithms are highly procedural and spatial. When students physically act out or visually trace traversal steps, they internalize the queue and stack behaviors that define BFS and DFS, turning abstract data structures into concrete experiences.

• Common Core State Standards
• CSTA: 3B-AP-12
• CCSS.ELA-LITERACY.RST.11-12.3

• 20–30 min
• Pairs → Whole Class
• 4 activities

Activity 01

• Simulation Game
• 25 min · Whole Class

Simulation Game: Human BFS and DFS Race

Draw a connected graph with 10 labeled nodes on a whiteboard. Two volunteer traversers start at the same source node: one uses BFS rules and explores all current neighbors before going deeper, the other uses DFS rules and goes deep before backing up. The class acts as the queue or stack, calling out which node each traverser visits next.

Differentiate between the applications of BFS and DFS in real-world problems.

Facilitation Tip

During the Human BFS and DFS Race, have students physically form a queue and stack using their bodies to reinforce the data structure behaviors that drive each algorithm.

What to look for

Provide students with a small, simple graph diagram (e.g., 5-7 nodes). Ask them to trace the order of node visits using BFS starting from a specific node, and then repeat the trace for DFS. They should write down the sequence of visited nodes for each traversal.

• Apply
• Analyze
• Evaluate
• Create
• Social Awareness
• Decision-Making

Activity 02

• Simulation Game
• 30 min · Small Groups

Problem Solving: Social Network Degree of Separation

Give student groups a small social network graph of 10 to 15 nodes. Groups use BFS to find the shortest path between two specified people, recording each level of the BFS and the discovered path. Groups then discuss whether DFS would find the shortest path as reliably and why.

Analyze the time and space complexity of BFS and DFS on different graph structures.

Facilitation Tip

For the Social Network Degree of Separation activity, provide a small hand-drawn social network graph so students can mark visited nodes and backtrack as they calculate degrees of separation.

What to look for

Present students with two scenarios: 1) finding the fastest route on a map, and 2) finding all possible paths from point A to point B. Ask them to identify which algorithm, BFS or DFS, is more appropriate for each scenario and briefly explain why.

• Apply
• Analyze
• Evaluate
• Create
• Social Awareness
• Decision-Making

Activity 03

• Think-Pair-Share
• 20 min · Pairs

Think-Pair-Share: Traversal Application Matching

Present 6 real-world problems including finding the shortest web path between Wikipedia articles, detecting loops in a dependency graph, crawling a directory tree, and finding any valid maze solution. Pairs match each problem to BFS or DFS and justify the choice before sharing with the class.

Construct a graph traversal algorithm to solve a specific pathfinding problem.

Facilitation Tip

In the Think-Pair-Share, provide a clear rubric for matching scenarios to algorithms so students can justify their choices with evidence from the activity.

What to look for

In small groups, have students discuss the trade-offs between BFS and DFS in terms of memory usage. Prompt them with: 'When might DFS use significantly less memory than BFS, and when might BFS be more memory-intensive?'

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

Activity 04

• Gallery Walk
• 30 min · Pairs

Gallery Walk: Graph Complexity Analysis Cards

Post graph structure cards around the room covering dense directed, sparse undirected, tree, and grid graphs. Students annotate each with BFS and DFS time and space complexity, noting where the two algorithms differ meaningfully. Class discussion focuses on how adjacency list versus matrix representations affect complexity.

Differentiate between the applications of BFS and DFS in real-world problems.

What to look for

Provide students with a small, simple graph diagram (e.g., 5-7 nodes). Ask them to trace the order of node visits using BFS starting from a specific node, and then repeat the trace for DFS. They should write down the sequence of visited nodes for each traversal.

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

A few notes on teaching this unit

Teachers often start with small, hand-drawn graphs to build intuition before introducing code or formal pseudocode. Avoid rushing to implementation details; focus first on the discovery order and why it matters. Research suggests that students grasp BFS and DFS more deeply when they first experience the algorithms kinesthetically, then connect those movements to data structures, and finally apply them to meaningful problems.

Successful learning looks like students confidently choosing between BFS and DFS for different scenarios, accurately tracing traversal orders on paper, and explaining the trade-offs between memory usage and path discovery. They should also recognize that the choice of algorithm affects the outcome in practical applications.

---

Watch Out for These Misconceptions

• During the Simulation: Human BFS and DFS Race, watch for students who claim BFS and DFS visit nodes in the same order.

  Use the physical race setup to have students record the exact sequence of node visits for both BFS and DFS on the same graph. Point out that BFS explores all nodes at the current level before moving deeper, while DFS follows a single path as far as possible.

• During the Problem Solving: Social Network Degree of Separation activity, watch for students who assume DFS must use recursion and BFS must use a while loop.

  Have students implement both DFS and BFS iteratively using explicit data structures (stack for DFS, queue for BFS) on their social network graphs to demonstrate that the looping mechanism is not tied to the algorithm.

• During the Think-Pair-Share: Traversal Application Matching activity, watch for students who associate graph algorithms only with geographic or map-based problems.

  Provide non-geographic examples in the matching cards, such as software dependency resolution or social network analysis, and ask students to justify why BFS or DFS fits each scenario beyond traditional maps.

---

Methods used in this brief

• Simulation Game
• Think-Pair-Share
• Gallery Walk