Graph Traversal

Graph traversal algorithms are the foundation of graph problem-solving, enabling us to systematically explore every node and edge in a graph. These techniques transform complex graph problems into manageable, step-by-step processes that are essential for technical interviews.

Real-World Analogy

Think of graph traversal like exploring a network of friends on social media. BFS is like finding all friends within 2 degrees of separation - you start with your direct friends, then their friends, level by level. DFS is like following a chain of recommendations - you dive deep into one friend’s network, exploring their connections completely before moving to another friend.

Visual Explanation

Breadth-First Search (BFS)

BFS explores the graph level by level, like ripples spreading in a pond:

  graph TD;
    A[Start] --> B[Level 1];
    A --> C[Level 1];
    B --> D[Level 2];
    B --> E[Level 2];
    C --> F[Level 2];
    C --> G[Level 2];
    D --> H[Level 3];
    E --> H;
    F --> I[Level 3];
    G --> I;

Depth-First Search (DFS)

DFS goes as deep as possible before backtracking, like exploring a maze:

  graph TD;
    A[Start] --> B[Deep Dive];
    B --> C[Continue Deep];
    C --> D[Maximum Depth];
    D --> E[Backtrack];
    E --> F[New Branch];
    F --> G[Continue Branch];

When to Use This Pattern

Use BFS when:

• You need the shortest path in an unweighted graph
• Problem asks for minimum steps or minimum operations
• You need to explore nodes level by level
• Problem involves finding connected components at specific distances

Use DFS when:

• You need to explore all possible paths
• Problem involves cycle detection
• You need topological sorting
• Problem requires checking reachability between nodes
• You need to find all solutions (backtracking)

Complexity Analysis

Time Complexity

• BFS:
  O(V + E)
  where V is vertices, E is edges
• DFS:
  O(V + E)
  where V is vertices, E is edges
• Each vertex and edge is visited exactly once

Space Complexity

• BFS:
  O(V)
  for the queue in worst case
• DFS:
  O(V)
  for the recursion stack or explicit stack
• Visited Set:
  O(V)
  to track visited nodes

Common Mistakes

1. Forgetting to mark nodes as visited: This leads to infinite loops in graphs with cycles
2. Wrong graph representation: Using adjacency matrix for sparse graphs wastes memory
3. Not handling disconnected components: Some graphs have multiple disconnected parts
4. Mixing up BFS and DFS: Using DFS when shortest path is needed, or vice versa
5. Edge case handling: Empty graphs, single nodes, or self-loops need special attention

Next Steps

Ready to master graph traversal? Check out our comprehensive Code Templates for multi-language implementations and Practice Problems to apply these concepts to real interview questions.