Graph Traversal: Deep Dive into DFS and BFS

Graph traversal is fundamental to solving many algorithmic problems. Understanding DFS and BFS is crucial.

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking.

Recursive Implementation

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

Iterative Implementation

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node)
            stack.extend(reversed(graph[node]))

Breadth-First Search (BFS)

BFS explores all neighbors before moving to the next level.

from collections import deque

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

When to Use Which?

Use DFS when:

- Finding paths

- Detecting cycles

- Topological sorting

- Memory is limited (recursive stack)

Use BFS when:

- Finding shortest paths (unweighted graphs)

- Level-order traversal

- Finding minimum steps

Common Applications

1. **DFS:** Maze solving, cycle detection, topological sort

2. **BFS:** Shortest path, level-order traversal, social networks

Both are essential tools in your algorithmic toolkit!