🌲 BFS & DFS Fundamentals

🎯 What are BFS and DFS?

BFS (Breadth-First Search) and DFS (Depth-First Search) are the two fundamental graph traversal algorithms. BFS explores neighbors level by level using a queue, while DFS explores as far as possible along each branch before backtracking using a stack (or recursion).

Time: O(V+E) for both | Space: O(V) for both

Core Concepts

BFS: "Wave propagation" - finds shortest path in unweighted graphs. Uses a queue (FIFO).
DFS: "Maze exploration" - uses stack (LIFO) or recursion. Great for topological sorting and cycle detection.

📌 Graph Traversal📌 Queue vs Stack📌 O(V+E) Time📌 Connected Components

from collections import deque

# BFS - Queue based
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

# DFS - Recursive
def dfs_recursive(graph, node, visited=None):
    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

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
print("BFS:", bfs(graph, 'A'))  # ['A','B','C','D','E','F']
print("DFS:", dfs_recursive(graph, 'A'))  # ['A','B','D','E','F','C']

🔵 BFS - Breadth First Search

🎯 How BFS Works

BFS explores vertices in order of their distance from the source. It uses a queue to process nodes level by level. This guarantees the shortest path (minimum number of edges) to every reachable node in an unweighted graph.

Data Structure: Queue (FIFO)
Level-order traversal: All nodes at distance k are processed before nodes at distance k+1
Shortest Path: First time a node is visited is via the shortest path

# BFS with shortest path reconstruction
def bfs_shortest_path(graph, start, target):
    visited = {start}
    queue = deque([(start, [start])])
    while queue:
        node, path = queue.popleft()
        if node == target:
            return path
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return None

🟣 DFS - Depth First Search

🎯 How DFS Works

DFS explores as far as possible along each branch before backtracking. It uses a stack (either explicitly or via recursion). DFS is memory efficient for deep graphs and useful for detecting cycles, topological sorting, and solving puzzles.

Data Structure: Stack (LIFO) or recursion
Backtracking: Natural for exploring all possibilities
Pre/Post-order: Can process nodes on entry and exit

# DFS - Iterative 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)
            # Add neighbors in reverse order for natural order
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    return result

⏱️ Time & Space Complexity

🎯 Complexity Analysis

Time Complexity (Both): O(V + E) using adjacency list — each vertex and edge processed once.
Space Complexity (BFS): O(V) for queue + visited set. Worst-case queue size = V.
Space Complexity (DFS Recursive): O(V) recursion stack (worst-case depth = V).
Space Complexity (DFS Iterative): O(V) for explicit stack.

⚖️ BFS vs DFS Comparison

BFS Shortest Path: Yes (unweighted graphs) | DFS No
BFS Memory: More (stores entire level) | DFS Less (only current path)
BFS Completeness: Always finds solution if exists | DFS May get stuck in infinite loops
BFS Use Cases: Shortest path, web crawling, social networks | DFS Topological sort, cycle detection, maze solving

💻 Multiple Implementations

# BFS on Grid (2D)
def bfs_grid(grid, start, target):
    rows, cols = len(grid), len(grid[0])
    directions = [(0,1),(1,0),(0,-1),(-1,0)]
    queue = deque([(start[0], start[1], 0)])  # (r,c,distance)
    visited = set()
    visited.add(start)
    while queue:
        r, c, dist = queue.popleft()
        if (r, c) == target:
            return dist
        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] != '#':
                visited.add((nr,nc))
                queue.append((nr,nc,dist+1))
    return -1

# DFS for connected components
def connected_components(graph):
    visited = set()
    components = []
    for node in graph:
        if node not in visited:
            component = dfs_recursive(graph, node, set())
            visited.update(component)
            components.append(component)
    return components

📊 Step-by-Step Visualization

🎯 Graph: A connected to B, C; B to D, E; C to F

BFS from A: Queue = [A] → process A → queue=[B,C] → process B → queue=[C,D,E] → process C → queue=[D,E,F] → process D/E/F → done.
DFS from A: Stack = [A] → pop A → push C,B (order matters) → pop B → push E,D → pop D → ... gives A,B,D,E,C,F or similar.

🎯 Applications of BFS & DFS

BFS: GPS navigation, social network friend suggestions, web crawling, peer-to-peer networks, minimum spanning tree (Prim's)
DFS: Solving puzzles/mazes, topological sorting, detecting cycles, finding strongly connected components (Kosaraju/Tarjan), generating permutations/combinations

🎯 Directed vs Undirected Graphs

Both BFS and DFS work on directed and undirected graphs. For undirected graphs, simply ensure you don't revisit the parent. For directed graphs, edges have direction — traversal only follows edge direction. Cycle detection in directed graphs requires tracking nodes in the current recursion stack (DFS).

# Cycle detection in directed graph using DFS
def has_cycle_directed(graph):
    visited = set()
    rec_stack = set()
    def dfs(node):
        visited.add(node)
        rec_stack.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in rec_stack:
                return True
        rec_stack.remove(node)
        return False
    for node in graph:
        if node not in visited:
            if dfs(node):
                return True
    return False

🔄 Iterative vs Recursive DFS

Recursive DFS: Cleaner code, but risk of stack overflow for deep graphs (>1000 depth).
Iterative DFS: Uses explicit stack, no recursion limit issues, slightly more verbose.
Performance: Iterative often faster (no function call overhead).

🎨 Graph Coloring & Detection

🎯 Bipartite Graph Check (BFS/DFS)

A graph is bipartite if vertices can be colored with 2 colors such that no adjacent vertices share the same color. BFS works perfectly: start with one color, assign opposite to neighbors. If conflict found → not bipartite.

def is_bipartite(graph):
    color = {}
    for node in graph:
        if node not in color:
            queue = deque([node])
            color[node] = 0
            while queue:
                curr = queue.popleft()
                for neighbor in graph[curr]:
                    if neighbor not in color:
                        color[neighbor] = 1 - color[curr]
                        queue.append(neighbor)
                    elif color[neighbor] == color[curr]:
                        return False
    return True

🔄 Bidirectional BFS

🎯 Two-Ended Search for Speed

For large graphs where both source and target are known, run BFS from both ends simultaneously. When frontiers meet, the path is found. Time complexity reduces from O(b^d) to O(b^(d/2)) — massive improvement for large search spaces.

🚀 Parallel BFS/DFS

🎯 Concurrent Graph Traversal

BFS level-by-level can be parallelized by processing all nodes at current level simultaneously. GPU implementations can achieve significant speedups. DFS is harder to parallelize due to its sequential nature but can be done with work-stealing.

💪 Practice & Problem Patterns

🎯 Classic BFS/DFS Problems

Number of Islands (LeetCode 200): DFS/BFS to count connected components.
Word Ladder (LeetCode 127): BFS for shortest transformation sequence.
Course Schedule (LeetCode 207): Cycle detection with DFS.
Pacific Atlantic Water Flow: Multi-source BFS/DFS.
Surrounded Regions: BFS/DFS from boundaries.
Binary Tree Level Order Traversal: BFS on trees.

# LeetCode 200 - Number of Islands
def numIslands(grid):
    if not grid: return 0
    rows, cols = len(grid), len(grid[0])
    visited = set()
    def dfs(r, c):
        if (r,c) in visited or r<0 or r>=rows or c<0 or c>=cols or grid[r][c]=='0':
            return
        visited.add((r,c))
        for dr,dc in [(0,1),(1,0),(0,-1),(-1,0)]:
            dfs(r+dr, c+dc)
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and (r,c) not in visited:
                dfs(r,c)
                count += 1
    return count