Computer Science · 12th Grade · Complex Algorithms and Optimization · Weeks 1-9

Graph Traversal Algorithms: BFS and DFS

Students explore Breadth-First Search (BFS) and Depth-First Search (DFS) algorithms for traversing graphs, understanding their applications.

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

About This Topic

Graph traversal is one of the most broadly applicable topics in computer science, underlying everything from social network analysis to route planning to compiler dependency resolution. Breadth-First Search explores all neighbors at the current level before moving deeper, using a queue as its core data structure. Depth-First Search follows a path as far as possible before backtracking, using a stack or recursion instead. Understanding both algorithms and when to apply each is essential for any student continuing to college CS or software engineering.

At the 12th-grade level, students move beyond treating graphs as abstract diagrams and learn to implement BFS and DFS in code, analyze their time and space complexity on different graph structures, and choose between them based on the problem's requirements. BFS guarantees the shortest path in unweighted graphs; DFS is better suited for detecting cycles, topological sorting, and exhaustive search.

Collaborative problem-solving works especially well here because graph problems are visual and benefit from shared reasoning. Group traversal activities on drawn graphs help students internalize visited-node tracking and queue versus stack behavior before implementing either algorithm.

Key Questions

1. Differentiate between the applications of BFS and DFS in real-world problems.
2. Analyze the time and space complexity of BFS and DFS on different graph structures.
3. Construct a graph traversal algorithm to solve a specific pathfinding problem.

Learning Objectives

• Compare the step-by-step execution of Breadth-First Search (BFS) and Depth-First Search (DFS) on a given graph, identifying differences in node visitation order.
• Analyze the time and space complexity of BFS and DFS algorithms for both adjacency list and adjacency matrix graph representations.
• Design and implement a BFS or DFS algorithm in Python to find the shortest path in an unweighted graph or detect a cycle in a directed graph.
• Evaluate the suitability of BFS versus DFS for solving specific pathfinding problems, such as finding the quickest route versus exploring all possible branches.
• Critique the efficiency of BFS and DFS implementations based on graph density and size, justifying choices for optimal performance.

Before You Start

Introduction to Data Structures

Why: Students need a foundational understanding of basic data structures like arrays, lists, and potentially stacks/queues to implement graph traversal algorithms.

Basic Programming Concepts (Python)

Why: Students must be able to write and understand code, including loops, conditional statements, and function calls, to implement BFS and DFS.

Introduction to Algorithms and Complexity

Why: Understanding Big O notation is crucial for analyzing the time and space complexity of BFS and DFS.

Key Vocabulary

Graph	A data structure consisting of a set of nodes (vertices) and a set of edges connecting pairs of nodes.
Breadth-First Search (BFS)	A graph traversal algorithm that explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. It uses a queue.
Depth-First Search (DFS)	A graph traversal algorithm that explores as far as possible along each branch before backtracking. It typically uses a stack or recursion.
Queue	A first-in, first-out (FIFO) data structure used in BFS to keep track of nodes to visit.
Stack	A last-in, first-out (LIFO) data structure used in DFS (or recursion) to keep track of nodes to visit or backtrack from.
Adjacency List	A representation of a graph where each node has a list of its adjacent nodes. This is often more space-efficient for sparse graphs.

Watch Out for These Misconceptions

Common Misconception

BFS and DFS visit the same nodes in the same order.

What to Teach Instead

BFS and DFS visit the same set of nodes in a connected graph but in different orders. More importantly, BFS guarantees shortest paths in unweighted graphs while DFS does not. The traversal order matters for many applications. Having students trace both algorithms on the same graph side by side makes the difference in discovery order concrete and memorable.

Common Misconception

DFS must use recursion and BFS must use a while loop.

What to Teach Instead

DFS is naturally expressed recursively because recursion uses the call stack, but DFS can also be implemented iteratively with an explicit stack data structure. BFS uses an iterative loop with a queue. Both algorithms are general search procedures distinguished by the data structure maintaining their frontier, not by their looping mechanism.

Common Misconception

Graph algorithms only apply to geographic or map-based problems.

What to Teach Instead

Graphs represent any relationship between entities: social connections, software dependency chains, state machines, and compilation order. Students who associate graphs only with maps miss the broad applicability of BFS and DFS. Presenting non-geographic examples like module dependency resolution or social network analysis broadens their mental model of when these algorithms apply.

Active Learning Ideas

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.

25 min·Whole Class

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.

30 min·Small Groups

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.

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

30 min·Pairs

Real-World Connections

• Google Maps and other navigation apps use BFS to find the shortest route between two points on a road network, treating intersections as nodes and roads as edges.
• Social media platforms like Facebook or LinkedIn employ graph traversal algorithms to suggest friends or connections by exploring the network of existing relationships.
• Cybersecurity analysts use DFS to trace the spread of malware or identify vulnerabilities within a network, systematically exploring potential attack paths.

Assessment Ideas

Exit Ticket

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.

Quick Check

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.

Discussion Prompt

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?'

Frequently Asked Questions

What is the difference between BFS and DFS in terms of data structures used?

BFS uses a queue (first-in, first-out) to maintain the frontier of nodes to visit, ensuring nodes are explored level by level. DFS uses a stack (last-in, first-out), either an explicit stack or the call stack via recursion, to explore as deep as possible before backtracking. The choice of data structure determines the traversal order and which applications each algorithm is suited for.

When should I use BFS instead of DFS for a graph problem?

Use BFS when you need the shortest path in an unweighted graph or when you want to explore nodes in order of their distance from the source. Use DFS when you need to detect cycles, perform topological sorting, explore all paths exhaustively, or when solutions are expected to be deep in the search space. BFS guarantees shortest paths; DFS guarantees complete exploration of all reachable nodes.

What is the time complexity of BFS and DFS?

Both BFS and DFS have O(V + E) time complexity, where V is the number of vertices and E is the number of edges. Each vertex is visited once and each edge is examined once in directed graphs, twice in undirected. Space complexity differs: BFS may require O(V) queue space in wide graphs, while DFS may require O(V) stack space in deep graphs. The practical difference depends on graph shape.

How does physically acting out graph traversals help students learn these algorithms?

Graph traversal is difficult to visualize from code because visited-node tracking and queue or stack management happen implicitly. When students physically act as the queue or stack and move through a drawn graph, the traversal order, frontier data structure role, and visited-set logic become tangible. Students who have acted out both algorithms rarely confuse their traversal orders in subsequent assignments.