BFS and DFS | Graph Traversal Algorithms Complete Guide

Introduction

”Two Pillars of Graph Traversal”

BFS and DFS are fundamental graph/tree traversal algorithms. They appear very frequently in coding interviews and must be mastered.

---

1. BFS (Breadth-First Search)

What is BFS?

BFS visits nodes level by level, starting from nearest. Like ripples spreading outward when a stone is thrown in a pond. Used for finding shortest paths in unweighted graphs.

    1
   / \
  2   3
 / \
4   5

BFS order: 1 → 2 → 3 → 4 → 5 (level by level)

Python Implementation

BFS uses a queue to traverse level by level:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result

# Graph (adjacency list)
graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1],
    4: [2],
    5: [2]
}

print(bfs(graph, 1))  # [1, 2, 3, 4, 5]

BFS Characteristics:

• Traverses level by level (nearest nodes first)
• Guarantees shortest path (unweighted graphs)
• Uses queue (FIFO)
• May use more memory than DFS (wide graphs)

Shortest Path (Distance Calculation)

def bfs_shortest_path(graph, start, end):
    visited = {start: 0}  # node: distance
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        
        if node == end:
            return visited[end]
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited[neighbor] = visited[node] + 1
                queue.append(neighbor)
    
    return -1  # No path

# Test
print(bfs_shortest_path(graph, 1, 4))  # 2 (1→2→4)

---

2. DFS (Depth-First Search)

What is DFS?

DFS goes as deep as possible in one direction, then backtracks when there’s nowhere to go. Like following one wall in a maze until hitting a dead end, then backtracking.

    1
   / \
  2   3
 / \
4   5

DFS order: 1 → 2 → 4 → 5 → 3 (depth first)

Python Implementation (Recursive)

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

# Usage
visited = set()
result = []
dfs_recursive(graph, 1, visited, result)
print(result)  # [1, 2, 4, 5, 3]

Recursion Advantages:

• Concise and intuitive code
• Natural backtracking implementation

Recursion Disadvantages:

• Stack overflow risk with deep recursion
• Python default recursion limit: 1000 (changeable with sys.setrecursionlimit)

Python Implementation (Stack)

Iterative implementation using explicit stack:

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

print(dfs_iterative(graph, 1))  # [1, 2, 4, 5, 3]

---

3. BFS vs DFS Comparison

Feature	BFS	DFS
Data Structure	Queue	Stack/Recursion
Traversal Order	Level by level	Depth first
Shortest Path	Yes	No
Memory	More	Less
Implementation	Iterative	Recursive
Time Complexity	O(V+E)	O(V+E)

When to use BFS?

• ✅ Shortest path
• ✅ Level traversal
• ✅ Nearest node

When to use DFS?

• ✅ Explore all paths
• ✅ Backtracking
• ✅ Cycle detection

---

4. Problem Solving

Problem 1: Maze Escape (BFS)

from collections import deque

def maze_escape(maze):
    """
    Find shortest distance from (0,0) to (n-1,m-1)
    1: walkable, 0: wall
    """
    n, m = len(maze), len(maze[0])
    queue = deque([(0, 0, 1)])  # (row, col, distance)
    visited = {(0, 0)}
    
    # Up, down, left, right
    directions = [(-1,0), (1,0), (0,-1), (0,1)]
    
    while queue:
        r, c, dist = queue.popleft()
        
        if r == n-1 and c == m-1:
            return dist
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            
            if (0 <= nr < n and 0 <= nc < m and 
                maze[nr][nc] == 1 and (nr, nc) not in visited):
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))
    
    return -1

# Test
maze = [
    [1, 0, 1, 1, 1],
    [1, 0, 1, 0, 1],
    [1, 0, 1, 0, 1],
    [1, 1, 1, 0, 1]
]
print(maze_escape(maze))  # 9

Problem 2: Number of Islands (DFS)

def count_islands(grid):
    """
    Count connected regions of 1s
    """
    if not grid:
        return 0
    
    n, m = len(grid), len(grid[0])
    visited = set()
    count = 0
    
    def dfs(r, c):
        if (r < 0 or r >= n or c < 0 or c >= m or
            grid[r][c] == 0 or (r, c) in visited):
            return
        
        visited.add((r, c))
        
        # Explore 4 directions
        dfs(r-1, c)
        dfs(r+1, c)
        dfs(r, c-1)
        dfs(r, c+1)
    
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 1 and (i, j) not in visited:
                dfs(i, j)
                count += 1
    
    return count

# Test
grid = [
    [1, 1, 0, 0, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 1, 1]
]
print(count_islands(grid))  # 3

Problem 3: All Paths (DFS)

def all_paths(graph, start, end):
    """
    Find all paths from start to end
    """
    def dfs(node, path):
        if node == end:
            result.append(path[:])
            return
        
        for neighbor in graph[node]:
            if neighbor not in path:
                path.append(neighbor)
                dfs(neighbor, path)
                path.pop()  # Backtrack
    
    result = []
    dfs(start, [start])
    return result

# Test
graph = {1: [2, 3], 2: [4], 3: [4], 4: []}
print(all_paths(graph, 1, 4))
# [[1, 2, 4], [1, 3, 4]]

---

5. Practical Tips

Coding Interview Tips

# ✅ Always track visited
# Prevents infinite loops in cycles

# ✅ Choose data structure
# BFS: collections.deque (O(1) popleft)
# DFS: list (O(1) pop) or recursion

# ✅ Grid problems
# Use directions array for 4/8 directions
directions = [(-1,0), (1,0), (0,-1), (0,1)]  # 4-way
# directions = [(-1,-1), (-1,0), (-1,1), (0,-1), 
#               (0,1), (1,-1), (1,0), (1,1)]  # 8-way

# ✅ Level-order processing
# Track level size in BFS
level_size = len(queue)
for _ in range(level_size):
    node = queue.popleft()

Common Patterns

Pattern 1: BFS Template

from collections import deque

def bfs_template(graph, start):
    visited = set([start])
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        
        # Process node
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Pattern 2: DFS Template

def dfs_template(graph, node, visited):
    visited.add(node)
    
    # Process node
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_template(graph, neighbor, visited)

---

Summary

Key Points

1. BFS: Uses queue, shortest path, O(V+E)
2. DFS: Uses stack/recursion, all paths, O(V+E)
3. Selection: Shortest path → BFS, all paths → DFS
4. Implementation: BFS with queue, DFS with recursion is simpler

Time Complexity

Both BFS and DFS: O(V + E)

• V: number of vertices
• E: number of edges

Space Complexity

• BFS: O(V) - queue can hold entire level
• DFS (recursive): O(h) - recursion stack depth h
• DFS (iterative): O(V) - explicit stack

---

Recommended Problems

Beginner

• LeetCode 104: Maximum Depth of Binary Tree
• LeetCode 111: Minimum Depth of Binary Tree
• LeetCode 733: Flood Fill

Intermediate

• LeetCode 200: Number of Islands
• LeetCode 207: Course Schedule
• LeetCode 127: Word Ladder

Advanced

• LeetCode 301: Remove Invalid Parentheses
• LeetCode 126: Word Ladder II
• LeetCode 417: Pacific Atlantic Water Flow

---

Related Posts

• Graph Data Structure | Complete Guide
• Stack and Queue | LIFO and FIFO
• Tree Data Structure | Binary Tree and BST

---

Keywords

BFS, DFS, Breadth-First Search, Depth-First Search, Graph Traversal, Queue, Stack, Recursion, Shortest Path, Backtracking, Coding Interview, Algorithm