Computer Science · Grade 11 · Data Structures and Management · Term 3

Graphs: Traversal Algorithms (BFS/DFS)

Implement and compare Breadth-First Search (BFS) and Depth-First Search (DFS) algorithms for traversing graphs.

• Ontario Curriculum Expectations
• CS.HS.A.3
• CS.HS.A.4

About This Topic

Graphs represent connections in networks, from social media to road systems, and traversal algorithms like Breadth-First Search (BFS) and Depth-First Search (DFS) systematically visit all nodes. BFS uses a queue to explore level by level, making it perfect for shortest paths in unweighted graphs. DFS employs a stack or recursion to plunge deep into one branch before backtracking, useful for detecting cycles or topological sorts. Students implement both in code, compare outputs, and analyze complexities.

In the data structures unit, this topic extends prior work with lists and trees into dynamic graph operations. Key questions guide differentiation of strategies, complexity analysis on varied structures, and BFS for shortest paths. These build computational thinking, preparing students for advanced topics like AI pathfinding or database queries.

Active learning excels with this abstract content. When students code traversals collaboratively, visualize paths on interactive tools, or trace physical graphs with string, differences between level-wise and depth-first exploration become concrete. Peer debugging and group comparisons sharpen analysis skills and reveal real-world trade-offs.

Key Questions

1. Differentiate between BFS and DFS in terms of their exploration strategy and applications.
2. Analyze the time and space complexity of BFS and DFS on different graph structures.
3. Construct an algorithm to find the shortest path in an unweighted graph using BFS.

Learning Objectives

• Compare the step-by-step exploration strategies of Breadth-First Search (BFS) and Depth-First Search (DFS) when traversing a given graph.
• Analyze the time and space complexity of BFS and DFS algorithms for both adjacency list and adjacency matrix representations of a graph.
• Design and implement an algorithm using BFS to find the shortest path between two nodes in an unweighted graph.
• Evaluate the suitability of BFS versus DFS for specific graph problems, such as finding cycles or determining connectivity.

Before You Start

Introduction to Graphs

Why: Students need to understand graph terminology, including nodes, edges, directed vs. undirected graphs, and representations like adjacency lists and matrices.

Basic Data Structures (Lists, Stacks, Queues)

Why: Familiarity with lists, stacks, and queues is essential as these are the core data structures used to implement BFS and DFS.

Key Vocabulary

Graph Traversal	The process of visiting each node in a graph in a systematic way, ensuring no node is missed.
Breadth-First Search (BFS)	A graph traversal algorithm that explores neighbor nodes first before moving to the next level neighbors, typically using a queue.
Depth-First Search (DFS)	A graph traversal algorithm that explores as far as possible along each branch before backtracking, typically using a stack or recursion.
Queue	A First-In, First-Out (FIFO) data structure used in BFS to keep track of nodes to visit next.
Stack	A Last-In, First-Out (LIFO) data structure used in DFS (iterative implementation) to keep track of nodes to visit next.

Watch Out for These Misconceptions

Common Misconception

BFS and DFS always visit nodes in the same order.

What to Teach Instead

Order varies by starting node and neighbor listing. Tracing traversals on paper in pairs reveals level-by-level versus branch-deep patterns, helping students visualize queues and stacks actively.

Common Misconception

DFS finds the shortest path faster than BFS.

What to Teach Instead

BFS guarantees shortest paths in unweighted graphs; DFS may not. Group coding races on mazes demonstrate this, as students measure and debate path lengths, building evidence-based understanding.

Common Misconception

Recursion in DFS always leads to stack overflow.

What to Teach Instead

Overflow depends on graph depth, not inherent to DFS. Simulating stacks with physical cards in small groups shows safe depths, encouraging students to test limits experimentally.

Active Learning Ideas

Pair Programming: BFS Maze Challenge

Pairs sketch a simple grid graph as a maze, then code BFS to find the shortest path from start to goal. Switch roles for DFS version and compare paths printed from code. Discuss why paths differ.

35 min·Pairs

Small Groups: Complexity Comparison Lab

Groups generate sparse and dense graphs using adjacency lists. Implement BFS and DFS, measure execution time and memory on 100+ nodes. Chart results and predict for larger graphs.

45 min·Small Groups

Whole Class: Live Traversal Simulation

Project a graph on the board. Class votes on next node for BFS queue or DFS stack. Code live in Python, pausing for predictions. Replay with different starts.

30 min·Whole Class

Individual: Custom Graph Tester

Students build personal graphs from real scenarios like friend networks. Code both algorithms, output traversal orders, and note applications in a reflection log.

25 min·Individual

Real-World Connections

• Network engineers use BFS to find the shortest path for data packets in computer networks, ensuring efficient communication between devices.
• Social media platforms employ graph traversal algorithms, similar to DFS, to suggest friends or identify communities by exploring connections outward from a user's profile.
• GIS specialists utilize BFS to determine the shortest driving route between two points on a map, considering road networks as graphs.

Assessment Ideas

Quick Check

Provide students with a small, unweighted graph represented by an adjacency list. Ask them to trace the execution of BFS starting from a specific node, listing the order nodes are visited and the contents of the queue at each step. Then, ask them to do the same for DFS.

Discussion Prompt

Pose the following scenario: 'Imagine you are designing a system to detect if a user has access to a specific file in a complex directory structure. Which traversal algorithm, BFS or DFS, would be more efficient and why? Consider the potential depth of the directory structure.'

Exit Ticket

On a slip of paper, have students write down one key difference between BFS and DFS in terms of their exploration strategy. Then, ask them to name one specific application where BFS is preferred over DFS, and one where DFS is preferred over BFS.

Frequently Asked Questions

What are the main differences between BFS and DFS?

BFS explores graphs level by level with a queue, ideal for shortest paths in unweighted graphs, while DFS goes deep first with a stack or recursion, suited for cycle detection or puzzles. Both have O(V+E) complexity, but BFS uses more space for wide graphs, DFS less for deep ones. Students compare via coded examples on varied structures.

How do you implement BFS and DFS in Python?

Use collections.deque for BFS queue, visiting neighbors level-wise. For DFS, use recursion or a stack list.pop(). Handle visited sets to avoid cycles. Test on adjacency lists: BFS suits breadth, DFS depth. Provide starter code for graphs, let students adapt for shortest path or order output.

What are real-world applications of BFS and DFS?

BFS powers GPS shortest routes, social network degrees of separation, and puzzle solvers like Rubik's Cube. DFS fits web crawlers, deadlock detection in OS, and maze generators. In Ontario curriculum, link to data management: BFS for efficient queries, DFS for exhaustive searches in networks or databases.

How can active learning help students grasp BFS and DFS?

Hands-on pair coding of traversals on visual graphs, like mazes or networks, makes queue versus stack logic tangible. Small group labs timing algorithms on real data reveal trade-offs. Whole-class simulations with predictions build intuition, while debugging fosters problem-solving over passive lectures.