BFS/DFS Traversal — Implement BFS/DFS traversal using queue/stack patterns (intro) - Python

SECTION 1

Historical Context & Motivation

Imagine you are dropped into a massive corn maze with dozens of branching paths. How would you guarantee that you find the exit? You could explore one path all the way to a dead end before backtracking, or you could check every path one step at a time. These two intuitions are the heart of graph traversal, one of the most fundamental problems in computer science. The algorithms that solve this problem — Breadth-First Search (BFS) and Depth-First Search (DFS) — were formalized over several decades, drawing on ideas from mathematics, electrical engineering, and early artificial intelligence.

1736 • Euler and the Königsberg Bridges

Leonhard Euler solved the famous Seven Bridges of Königsberg problem, effectively inventing graph theory. His work showed that many real-world problems can be modeled as networks of nodes and edges.

1945 • Depth-First Search Formalized

French mathematician Charles Pierre Trémaux developed a systematic method for navigating mazes that later became recognized as the first formal DFS algorithm. His rule — always follow a single path until you must backtrack — is still the core idea today.

1959 • BFS for Shortest Paths

Edward F. Moore published a paper on finding the shortest path out of a maze using a layer-by-layer exploration technique. This approach became the standard BFS algorithm used in networking, GPS, and game AI.

1972 • Tarjan's DFS Applications

Robert Tarjan used DFS as the backbone for algorithms that detect strongly connected components and articulation points in graphs, earning the Turing Award for his work. DFS proved to be far more versatile than simple maze-solving.

Today, BFS and DFS are everywhere — from social media friend suggestions to web crawlers indexing the internet. The central question these algorithms answer is deceptively simple: given a starting point, how do we visit every reachable node in a graph exactly once? The difference between BFS and DFS lies in the order in which they visit those nodes, and that order is controlled by a single data structure choice: a queue or a stack.

SECTION 2

Core Principles & Definitions

Before writing any code, you need to understand four foundational ideas that make BFS and DFS work. A graph is a collection of nodes (also called vertices) connected by edges. Think of cities connected by roads, or people connected by friendships. A tree is simply a special type of graph with no cycles — like a family tree where connections never loop back on themselves.

Queue (FIFO)

A queue follows First-In, First-Out order — like a lunch line. The first person to join is the first to be served. In Python, use collections.deque for efficient queues.

Stack (LIFO)

A stack follows Last-In, First-Out order — like a stack of plates. The most recently added plate is the first one removed. In Python, a regular list with append() and pop() works as a stack.

BFS — Level by Level

Breadth-First Search uses a queue to explore all neighbors of the current node before moving deeper. It spreads outward in concentric rings, like ripples in a pond.

DFS — As Deep as Possible

Depth-First Search uses a stack to dive down one path as far as it can go before backtracking. It's like exploring a cave system — you follow one tunnel to its end before trying another.

Visited Set

Both algorithms maintain a visited set to remember which nodes have already been processed. Without it, you could loop forever in a graph with cycles.

✦

KEY TAKEAWAY

Think of BFS like texting all your friends at once and waiting for all their replies before texting their friends. DFS is like calling one friend, then immediately calling whoever they recommend, going deeper and deeper down the chain before coming back. The only difference between the two algorithms in code is whether you use a queue (BFS) or a stack (DFS) to decide which node to visit next.

SECTION 3

Visual Explanation — BFS vs DFS Traversal Order

Both algorithms visit the same six nodes but in a different order. BFS visits all nodes at the same depth before going deeper (A, then B and C, then D, E, and F). DFS dives down the left branch (A → B → D → E) before backtracking to explore the right branch (C → F). The circled numbers show the visitation order.

Notice how the same tree structure produces two completely different traversal orders. The BFS side (left, in cyan) processes nodes in order of distance from the root — all nodes one step away first, then all nodes two steps away. The DFS side (right, in violet) follows a single branch all the way to the leaves before coming back to try another branch. This difference arises entirely from the choice of data structure: a queue for BFS ensures older (shallower) nodes are processed first, while a stack for DFS ensures the most recently discovered (deeper) node is processed first.

SECTION 4

How It Works — The Queue and Stack Patterns

Both BFS and DFS follow a remarkably similar template. You start at a node, mark it as visited, and add it to your data structure. Then, you enter a loop: remove one node from the data structure, process it, and add all of its unvisited neighbors. The loop ends when the data structure is empty. The only difference is which node you remove first.

BFS Algorithm Template

In BFS, you use a queue (FIFO). The Python code looks like this:

ℹ

BFS Code Pattern

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []

    while queue:
        node = queue.popleft()   # Remove from FRONT
        order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order

DFS Algorithm Template

In DFS, you swap the queue for a stack (LIFO). The change is surprisingly small — just one line differs:

ℹ

DFS Code Pattern

def dfs(graph, start):
    visited = set()
    stack = [start]
    order = []

    while stack:
        node = stack.pop()       # Remove from BACK
        if node not in visited:
            visited.add(node)
            order.append(node)

            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

    return order

Notice the structural similarity. In BFS, queue.popleft() removes the oldest item (front of the line). In DFS, stack.pop() removes the newest item (top of the stack). There is one subtle difference in the DFS version: we check if node not in visited when we pop rather than when we push, because the same node could be added to the stack multiple times before being visited. Both patterns are correct and widely used.

TIME COMPLEXITY

T = O(V + E)

V = number of vertices (nodes), E = number of edges. Both BFS and DFS visit every node exactly once and examine every edge once, so they share the same time complexity.

SPACE COMPLEXITY

S = O(V)

In the worst case, the queue (BFS) or stack (DFS) could hold all V nodes. The visited set also stores up to V entries, so total space is proportional to the number of nodes.

SECTION 5

Step-by-Step Trace — Watching the Queue and Stack in Action

The best way to understand BFS and DFS is to trace through them by hand on a concrete graph. Below is a diagram showing our sample graph represented as an adjacency list — a Python dictionary where each key is a node and its value is a list of neighbors.

This diagram shows the complete BFS trace as a step-by-step table, with the queue state and visited set at each step. The DFS trace below uses the same graph but with a stack, producing a completely different order. Note how the queue preserves the level-by-level order while the stack causes the algorithm to jump to the most recently discovered node.

Pay attention to step 2 in the BFS trace. After dequeuing B, its unvisited neighbors D and E join the back of the queue, behind C. This means C (a level-1 node) gets processed before D and E (level-2 nodes). In the DFS trace, the stack produces the opposite effect: after pushing B and C, C is on top and gets popped first, causing DFS to dive down C's branch immediately.

💡

Pro Tip

When tracing by hand, draw a small table with columns for Step, Action, Data Structure, and Visited. This helps you predict what the code will do and is a great way to debug traversal algorithms.

SECTION 6

Worked Example — Finding All Reachable Users in a Social Network

Suppose you are building a social network feature that finds all users reachable from a given person through mutual friendships. The friendships form an undirected graph. Let's use BFS to find everyone reachable from "Alice" and determine the shortest friendship distance to each person.

BFS — Social Network Reachability

1
Step 1 — Define the Graph

Represent friendships as an adjacency list in Python:friends = { 'Alice': ['Bob', 'Carol'], 'Bob': ['Alice', 'Dave', 'Eve'], 'Carol': ['Alice', 'Frank'], 'Dave': ['Bob'], 'Eve': ['Bob'], 'Frank': ['Carol'] }

6 users, 5 friendships (edges)
2
Step 2 — Initialize BFS Data Structures

Create a queue starting with 'Alice', a visited set containing 'Alice', and an empty result list. We also track the distance from Alice using a dictionary.from collections import deque queue = deque(['Alice']) visited = {'Alice'} distance = {'Alice': 0}

Queue: ['Alice'], Visited: {'Alice'}, Distance: {'Alice': 0}
3
Step 3 — Process the Queue

Dequeue 'Alice'. Her neighbors are 'Bob' and 'Carol'. Neither has been visited, so add both to the queue and visited set. Set their distance to distance['Alice'] + 1 = 1. Next, dequeue 'Bob'. His unvisited neighbors are 'Dave' and 'Eve' (distance 2). Then dequeue 'Carol', adding 'Frank' (distance 2). Continue until the queue is empty.

Queue empties after 6 iterations.
4
Step 4 — Read the Results

The distance dictionary now holds the shortest friendship chain from Alice to each person.# distance = { # 'Alice': 0, # 'Bob': 1, # 'Carol': 1, # 'Dave': 2, # 'Eve': 2, # 'Frank': 2 # }

All 6 users are reachable. Maximum distance is 2 (Dave, Eve, Frank are 'friends of friends').
5
Step 5 — Full Code

from collections import deque def bfs_with_distance(graph, start): visited = {start} queue = deque([start]) distance = {start: 0} while queue: node = queue.popleft() for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) distance[neighbor] = distance[node] + 1 queue.append(neighbor) return distance print(bfs_with_distance(friends, 'Alice'))

Output: {'Alice': 0, 'Bob': 1, 'Carol': 1, 'Dave': 2, 'Eve': 2, 'Frank': 2}

SECTION 7

BFS vs DFS — When to Use Which

BFS and DFS are both correct traversal algorithms, but they shine in different situations. The table below summarizes the key trade-offs to help you choose the right tool for each problem.

Feature	BFS (Queue)	DFS (Stack)
Data structure	Queue (FIFO) — `collections.deque`	Stack (LIFO) — Python `list` or recursion
Traversal order	Level by level (breadth first)	Branch by branch (depth first)
Shortest path?	Yes — guaranteed for unweighted graphs	No — may find a longer path first
Memory usage	Can be high — stores entire frontier level	Usually lower — stores single path
Best for	Shortest path, nearest neighbor, level-order problems	Cycle detection, topological sort, maze generation, backtracking
Time complexity	O(V + E)	O(V + E)

BFS vs DFS comparison

✦

KEY TAKEAWAY

Think of BFS as using a megaphone at a concert — your message reaches everyone in the closest row first, then the second row, then the third. DFS is like passing a note down a single row of seats until it reaches the end, then coming back to try the next row. Use BFS when you need the shortest route and DFS when you need to fully explore one possibility before trying another.

SECTION 8

Connection to Advanced Algorithms

BFS and DFS are the building blocks for many advanced algorithms you will encounter as you continue studying computer science. Understanding these two patterns opens the door to solving much harder problems. Below is a preview of how they extend into more sophisticated territory.

Basic Concept	Advanced Extension	What It Adds
BFS (unweighted shortest path)	Dijkstra's Algorithm	Handles weighted edges using a priority queue instead of a regular queue
DFS (explore all paths)	Backtracking	Adds constraint checking to prune invalid branches early (e.g., Sudoku solvers)
DFS (graph structure)	Topological Sort	Orders tasks so that dependencies come first (course prerequisites, build systems)
BFS (level-order)	*A Search**	Adds a heuristic estimate to guide the search toward the goal faster (GPS navigation)

From BFS/DFS to advanced algorithms

You will also encounter a recursive version of DFS that uses the call stack instead of an explicit stack variable. In recursive DFS, each function call acts as a frame on the call stack, and returning from a call is the equivalent of popping. Recursive DFS is elegant and compact, but the iterative (explicit stack) version you learned here is safer for large graphs because it avoids Python's recursion depth limit.

ℹ

Looking Ahead

Once you are comfortable with BFS and DFS, try implementing Dijkstra's algorithm. It is essentially BFS with a priority queue (Python's heapq module) that always processes the lowest-cost node next, instead of the oldest or the newest.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

In your own words, explain why BFS guarantees finding the shortest path in an unweighted graph, but DFS does not. Use the idea of how a queue and a stack process nodes differently to support your answer.

Show answer

BFS uses a queue, which processes nodes in FIFO order. Because nodes at distance 1 are enqueued before nodes at distance 2, and distance 2 nodes before distance 3, and so on, BFS always finishes exploring every node at depth d before touching any node at depth d + 1. The first time BFS reaches a node is guaranteed to be via the shortest path. DFS uses a stack (LIFO), which means it immediately dives deeper rather than finishing a level. It may reach a node via a long detour before finding a shorter path, so it cannot guarantee shortest paths.

Question 2: BASIC CALCULATION

Given the following graph, trace through BFS starting from node 1 and write the order in which nodes are visited. Also show the queue state at each step.


graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 4, 5],
    4: [2, 3],
    5: [3]
}

Show answer

Start: Queue=[1], Visited={1}. Step 1: Dequeue 1, enqueue 2 and 3 → Queue=[2,3], Visited={1,2,3}. Step 2: Dequeue 2, enqueue 4 (1 already visited) → Queue=[3,4], Visited={1,2,3,4}. Step 3: Dequeue 3, enqueue 5 (1 and 4 already visited) → Queue=[4,5], Visited={1,2,3,4,5}. Step 4: Dequeue 4, no new neighbors → Queue=[5]. Step 5: Dequeue 5, no new neighbors → Queue=[]. Final BFS order: 1 → 2 → 3 → 4 → 5.

Question 3: INTERMEDIATE

Write a Python function dfs_iterative(graph, start) that uses an explicit stack to perform DFS and returns the list of visited nodes in order. Test it on the graph from Problem 2. Does it produce the same order as BFS? Why or why not?

Show answer

Here is the solution:


def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            order.append(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)
    return order

Running this on the graph with start=1 might produce 1 → 3 → 5 → 4 → 2 (the exact order depends on which neighbor is pushed last and therefore popped first). This order differs from BFS because the stack causes the algorithm to explore the most recently discovered node first, diving deep before coming back. BFS explores all distance-1 nodes before distance-2 nodes, which produces the level-by-level ordering 1 → 2 → 3 → 4 → 5.

Question 4: APPLIED

You are building a web crawler that starts at a homepage and follows all links on each page. You want to find every page within 3 clicks of the homepage. Which traversal algorithm should you use — BFS or DFS? Write the Python code that implements this, using a modified BFS that stops after depth 3. Assume get_links(url) returns a list of URLs found on a page.

Show answer

BFS is the correct choice because it naturally explores pages level by level (distance 0, then distance 1, etc.), so you can easily stop at depth 3. DFS would dive deep and might visit pages many clicks away before finding all pages at depth 1 or 2. Here is the code:


from collections import deque

def crawl(start_url, max_depth=3):
    visited = {start_url}
    queue = deque([(start_url, 0)])
    pages = []

    while queue:
        url, depth = queue.popleft()
        pages.append(url)
        if depth < max_depth:
            for link in get_links(url):
                if link not in visited:
                    visited.add(link)
                    queue.append((link, depth + 1))
    return pages

By storing a (url, depth) tuple in the queue, we track how many clicks each page is from the start. When depth equals max_depth, we stop adding new links, ensuring we never go beyond 3 clicks.

Question 5: CRITICAL THINKING

Consider a graph where every node connects to every other node (a complete graph with V nodes). How many edges does this graph have? Analyze the time and space complexity of running BFS on it. Then explain: for a complete graph, is there any practical difference between BFS and DFS in terms of the number of nodes at each 'level' of the traversal?

Show answer

A complete graph with V nodes has V × (V − 1) ÷ 2 edges (each pair of nodes shares one edge). Running BFS starting from any node, level 0 has 1 node (the start), and level 1 has V − 1 nodes (every other node is a direct neighbor). There is no level 2 because every node is already reachable in one step. Time complexity is O(V + E) = O(V + V²/2) = O(V²). Space complexity is O(V) for the visited set and queue, but the queue briefly holds V − 1 nodes at once. For DFS, the stack also holds up to V − 1 entries. In a complete graph, BFS finishes in just 2 levels and DFS finishes in V steps by popping one node at a time. The total work is the same (every edge is examined once), but BFS's queue balloons to size V − 1 on the first step, while DFS processes nodes more gradually. In practice, neither has a meaningful advantage on a complete graph.

SUMMARY

Lesson Summary

Summary

BFS (Breadth-First Search) and DFS (Depth-First Search) are the two fundamental ways to explore a graph or tree. BFS uses a queue (FIFO) to visit nodes level by level, guaranteeing the shortest path in unweighted graphs. DFS uses a stack (LIFO) to dive as deep as possible before backtracking, making it ideal for tasks like cycle detection and backtracking.

Both algorithms share the same O(V + E) time complexity and rely on a visited set to prevent infinite loops. The code templates are nearly identical — the only structural change is swapping queue.popleft() (BFS) for stack.pop() (DFS). Mastering these two patterns gives you the foundation for advanced algorithms like Dijkstra's, A* Search, and topological sort.