BFS vs DFS: When to Use Each with Examples

BFS and DFS are the two foundational graph traversal algorithms. Every other graph algorithm — Dijkstra, Bellman-Ford, topological sort, cycle detection, connected components — is built on one of them. Knowing not just how they work but when to choose each is what separates a passing answer from a strong one.

The Core Difference

BFS (Breadth-First Search) explores all neighbors at the current depth before going deeper. It uses a queue. It finds the shortest path in unweighted graphs.

DFS (Depth-First Search) goes as deep as possible down each branch before backtracking. It uses a stack (or the call stack via recursion). It’s the foundation for topological sort, cycle detection, and connected components.

BFS Implementation

from collections import deque

def bfs(graph: dict, start: int) -> list:
    """
    Breadth-first search returning nodes in order visited.
    graph: adjacency list {node: [neighbors]}
    """
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)

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

    return order

def bfs_shortest_path(graph: dict, start: int, end: int) -> list | None:
    """
    Find shortest path between start and end in an unweighted graph.
    Returns the path as a list, or None if no path exists.
    Time: O(V + E), Space: O(V)
    """
    if start == end:
        return [start]

    visited = {start}
    # Store (current_node, path_to_current_node)
    queue = deque([(start, [start])])

    while queue:
        node, path = queue.popleft()

        for neighbor in graph[node]:
            if neighbor == end:
                return path + [neighbor]
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None  # No path exists

# Example
graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 4],
    3: [1],
    4: [1, 2]
}
print(bfs_shortest_path(graph, 0, 3))  # [0, 1, 3]
print(bfs_shortest_path(graph, 3, 4))  # [3, 1, 4]

DFS Implementation

def dfs_recursive(graph: dict, node: int, visited: set = None) -> list:
    """
    Recursive DFS. Returns nodes in order visited.
    Time: O(V + E), Space: O(V) for recursion stack
    """
    if visited is None:
        visited = set()

    visited.add(node)
    result = [node]

    for neighbor in graph[node]:
        if neighbor not in visited:
            result.extend(dfs_recursive(graph, neighbor, visited))

    return result

def dfs_iterative(graph: dict, start: int) -> list:
    """
    Iterative DFS using explicit stack.
    Use this for large graphs to avoid recursion limit (Python default: 1000).
    """
    visited = set()
    stack = [start]
    order = []

    while stack:
        node = stack.pop()  # LIFO — this is what makes it DFS vs BFS
        if node in visited:
            continue
        visited.add(node)
        order.append(node)

        # Push neighbors in reverse order to maintain left-to-right traversal
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)

    return order

When to Use BFS vs DFS

Scenario	Use	Why
Shortest path in unweighted graph	BFS	BFS explores by increasing distance; first time you reach a node is via shortest path
Cycle detection	DFS	Back edges (reaching a node in current DFS path) indicate cycles
Topological sort	DFS	Post-order DFS naturally produces reverse topological order
Connected components	Either	Both explore all reachable nodes; DFS slightly simpler with recursion
Maze solving	DFS (find any path), BFS (find shortest path)	Depends on requirement
Level-order traversal (trees)	BFS	Each BFS level = one tree level
Detect if path exists	Either	DFS simpler; BFS if you also need the path
Very deep graphs (10^6 depth)	BFS or iterative DFS	Recursive DFS hits Python recursion limit at ~1000
Wide graphs (high branching factor)	DFS	BFS memory usage = O(branching_factor ^ depth); can be huge

Complexity Analysis

Both BFS and DFS are O(V + E) time and O(V) space where V = vertices and E = edges.

Space distinction:

BFS: queue holds the current frontier — worst case O(V) for a wide tree
DFS: recursion stack depth = longest path — O(V) worst case for a linear chain, O(log V) for a balanced tree

Common Interview Patterns Using BFS

Grid BFS (Number of Islands, Rotten Oranges, Minimum Steps)

def bfs_grid(grid: list[list[int]], start_r: int, start_c: int) -> int:
    """
    BFS on a 2D grid. Returns number of steps to explore all reachable cells.
    Template for: minimum steps problems, multi-source BFS, level-by-level processing.
    """
    rows, cols = len(grid), len(grid[0])
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # Right, left, down, up
    visited = set([(start_r, start_c)])
    queue = deque([(start_r, start_c, 0)])  # (row, col, steps)

    while queue:
        r, c, steps = queue.popleft()

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                    and (nr, nc) not in visited
                    and grid[nr][nc] != 0):  # 0 = wall/obstacle
                visited.add((nr, nc))
                queue.append((nr, nc, steps + 1))

    return len(visited)

Common Interview Patterns Using DFS

Path Problems

def has_path_with_constraint(graph: dict, start: int, end: int,
                              constraint: callable) -> bool:
    """
    DFS to find if a path exists where all nodes satisfy constraint.
    Template for: word ladder variants, path sum in trees.
    """
    def dfs(node, visited):
        if node == end:
            return True
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited and constraint(neighbor):
                if dfs(neighbor, visited):
                    return True
        return False

    return dfs(start, {start})

Multi-Source BFS

Start BFS from multiple sources simultaneously. Classic example: Rotten Oranges — find minimum minutes to rot all fresh oranges, where all rotten oranges spread simultaneously.

def multi_source_bfs(grid: list[list[int]]) -> int:
    """
    0 = empty, 1 = fresh orange, 2 = rotten orange.
    Find minimum minutes until all oranges rot.
    """
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh_count = 0

    # Initialize: add ALL rotten oranges to queue at time=0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))
            elif grid[r][c] == 1:
                fresh_count += 1

    if fresh_count == 0:
        return 0

    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    minutes = 0

    while queue:
        r, c, time = queue.popleft()
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh_count -= 1
                minutes = time + 1
                queue.append((nr, nc, time + 1))

    return minutes if fresh_count == 0 else -1

Practice Problems

BFS:

LeetCode 102: Binary Tree Level Order Traversal
LeetCode 127: Word Ladder (BFS on implicit graph)
LeetCode 994: Rotting Oranges (multi-source BFS)
LeetCode 286: Walls and Gates (multi-source BFS)

DFS:

LeetCode 200: Number of Islands (DFS flood fill)
LeetCode 133: Clone a Graph
LeetCode 207: Course Schedule (cycle detection)
LeetCode 417: Pacific Atlantic Water Flow