Graph Traversal (DFS/BFS)

Graph traversal is the process of visiting all vertices in a graph. Depth-First Search (DFS) and Breadth-First Search (BFS) are the two fundamental graph traversal algorithms.

Why This Matters in Interviews

Graph traversal is essential because:

• Graph problems: Most graph problems use DFS or BFS
• Algorithm foundation: Basis for many graph algorithms (shortest path, cycles, connectivity)
• Problem patterns: Different problems require different traversal strategies
• Implementation skills: Tests understanding of stacks, queues, and recursion

Interviewers use graph traversal to assess your understanding of graphs, your ability to choose the right algorithm, and your implementation skills.

Core Concepts

• DFS (Depth-First Search): Explores as far as possible along each branch
• BFS (Breadth-First Search): Explores level by level, closest nodes first
• Visited tracking: Prevent revisiting nodes
• Adjacency representation: Adjacency list vs adjacency matrix
• Connected components: Finding all connected parts of graph
• Cycle detection: Using traversal to detect cycles
• Path finding: Finding paths between nodes

Detailed Explanation

Graph Representation

1// Adjacency List (most common)
2class Graph {
3  private adjList: Map<number, number[]>;
4  
5  constructor() {
6    this.adjList = new Map();
7  }
8  
9  addVertex(v: number): void {
10    if (!this.adjList.has(v)) {
11      this.adjList.set(v, []);

Depth-First Search (DFS)

Recursive:

1function dfsRecursive(graph: Map<number, number[]>, start: number): number[] {
2  const result: number[] = [];
3  const visited = new Set<number>();
4  
5  function dfs(node: number): void {
6    visited.add(node);
7    result.push(node);
8    
9    for  neighbor  graphnode

Iterative:

1function dfsIterative(graph: Map<number, number[]>, start: number): number[] {
2  const result: number[] = [];
3  const visited = new Set<number>();
4  const stack: number[] = [start];
5  
6  while (stack.length > 0) {
7    const node = stack.pop()

Breadth-First Search (BFS)

1function bfs(graph: Map<number, number[]>, start: number): number[] {
2  const result: number[] = [];
3  const visited = new Set<number>();
4  const queue: number[] = [start];
5  visited.add(start);
6  
7  while (queue.length > 0) {
8     node  queue

BFS with Level Information

1function bfsLevels(graph: Map<number, number[]>, start: number): number[][] {
2  const levels: number[][] = [];
3  const visited = new Set<number>();
4  const queue: number[] = [start];
5  visited.add(start);
6  
7  while (queue.length >

Examples

Find Connected Components

function connectedComponents(graph: Map<number, number[]>): number[][] {
  const components: number[][] = [];
  const visited = new Set<number>();
  
  function dfs(node: number, component: number[]): void {
    visited.add(node);
    component.push(node);
    
    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        dfs(neighbor, component);
      }
    }
  }
  
  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      const component: number[] = [];
      dfs(node, component);
      components.push(component);
    }
  }
  
  return components;
}

// Time: O(V + E)

Detect Cycle in Undirected Graph

function hasCycleUndirected(graph: Map<number, number[]>): boolean {
  const visited = new Set<number>();
  
  function dfs(node: number, parent: number | null): boolean {
    visited.add(node);
    
    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor, node)) {
          return true;
        }
      } else if (neighbor !== parent) {
        // Back edge found (not parent)
        return true;
      }
    }
    
    return false;
  }
  
  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      if (dfs(node, null)) {
        return true;
      }
    }
  }
  
  return false;
}

Detect Cycle in Directed Graph

function hasCycleDirected(graph: Map<number, number[]>): boolean {
  const visited = new Set<number>();
  const recStack = new Set<number>();
  
  function dfs(node: number): boolean {
    visited.add(node);
    recStack.add(node);
    
    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor)) {
          return true;
        }
      } else if (recStack.has(neighbor)) {
        // Back edge in recursion stack = cycle
        return true;
      }
    }
    
    recStack.delete(node);
    return false;
  }
  
  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      if (dfs(node)) {
        return true;
      }
    }
  }
  
  return false;
}

Shortest Path (Unweighted Graph)

function shortestPath(
  graph: Map<number, number[]>, 
  start: number, 
  end: number
): number[] | null {
  const queue: number[] = [start];
  const visited = new Set<number>();
  const parent = new Map<number, number>();
  visited.add(start);
  
  while (queue.length > 0) {
    const node = queue.shift()!;
    
    if (node === end) {
      // Reconstruct path
      const path: number[] = [];
      let current: number | undefined = end;
      while (current !== undefined) {
        path.unshift(current);
        current = parent.get(current);
      }
      return path;
    }
    
    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        parent.set(neighbor, node);
        queue.push(neighbor);
      }
    }
  }
  
  return null; // No path found
}

// BFS guarantees shortest path in unweighted graph

Common Pitfalls

• Not marking visited: Infinite loops, revisiting nodes. Fix: Always mark visited before processing
• Wrong data structure: Using stack for BFS or queue for DFS. Fix: Stack for DFS, queue for BFS
• Cycle detection errors: Not handling back edges correctly. Fix: Track recursion stack for directed graphs
• Memory issues: Large graphs cause stack overflow. Fix: Use iterative DFS or limit depth
• Not handling disconnected graphs: Missing components. Fix: Check all unvisited nodes
• Path reconstruction: Not storing parent information. Fix: Use parent map for path finding

Interview Questions

Beginner

Q: Explain the difference between DFS and BFS. When would you use each?

A:

DFS (Depth-First Search):

• Strategy: Explore as deep as possible before backtracking
• Data structure: Stack (LIFO)
• Order: Visits nodes in depth order
• Use when: Finding paths, detecting cycles, topological sort, maze solving

BFS (Breadth-First Search):

• Strategy: Explore level by level, closest nodes first
• Data structure: Queue (FIFO)
• Order: Visits nodes in level order
• Use when: Shortest path (unweighted), level-order traversal, social networks

Key Differences:

Example:

Graph: A → B, A → C, B → D

DFS: A → B → D → C (goes deep first)
BFS: A → B → C → D (level by level)

Intermediate

Q: Implement DFS and BFS for a graph. How do you handle cycles and disconnected components?

A:

class GraphTraversal {
  private graph: Map<number, number[]>;
  
  constructor(graph: Map<number, number[]>) {
    this.graph = graph;
  }
  
  // DFS with cycle detection
  dfs(start: number): { order: number[], hasCycle: boolean } {
    const order: number[] = [];
    const visited = new Set<number>();
    const recStack = new Set<number>();
    let hasCycle = false;
    
    const dfsVisit = (node: number): void => {
      visited.add(node);
      recStack.add(node);
      order.push(node);
      
      for (const neighbor of this.graph.get(node) || []) {
        if (!visited.has(neighbor)) {
          dfsVisit(neighbor);
        } else if (recStack.has(neighbor)) {
          hasCycle = true;
        }
      }
      
      recStack.delete(node);
    };
    
    // Handle disconnected components
    for (const node of this.graph.keys()) {
      if (!visited.has(node)) {
        dfsVisit(node);
      }
    }
    
    return { order, hasCycle };
  }
  
  // BFS with level information
  bfs(start: number): { order: number[], levels: Map<number, number> } {
    const order: number[] = [];
    const visited = new Set<number>();
    const queue: number[] = [start];
    const levels = new Map<number, number>();
    
    visited.add(start);
    levels.set(start, 0);
    
    while (queue.length > 0) {
      const node = queue.shift()!;
      order.push(node);
      
      for (const neighbor of this.graph.get(node) || []) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          levels.set(neighbor, levels.get(node)! + 1);
          queue.push(neighbor);
        }
      }
    }
    
    // Handle disconnected components
    for (const node of this.graph.keys()) {
      if (!visited.has(node)) {
        queue.push(node);
        visited.add(node);
        levels.set(node, 0);
        
        while (queue.length > 0) {
          const current = queue.shift()!;
          order.push(current);
          
          for (const neighbor of this.graph.get(current) || []) {
            if (!visited.has(neighbor)) {
              visited.add(neighbor);
              levels.set(neighbor, levels.get(current)! + 1);
              queue.push(neighbor);
            }
          }
        }
      }
    }
    
    return { order, levels };
  }
}

Key points:

• Cycle detection: Use recursion stack for directed, parent tracking for undirected
• Disconnected components: Check all unvisited nodes
• Level tracking: Store distance/level in BFS

Senior

Q: Design a graph traversal system for a social network with millions of users. How do you handle large-scale traversal, implement friend suggestions, and optimize for performance?

A:

class SocialNetworkTraversal {
  private graph: DistributedGraph;
  private cache: Cache;
  private batchSize: number = 1000;
  
  constructor(graph: DistributedGraph, cache: Cache) {
    this.graph = graph;
    this.cache = cache;
  }
  
  // BFS with depth limit for friend suggestions
  async getFriendSuggestions(userId: number, maxDepth: number = 2): Promise<number[]> {
    const cacheKey = `suggestions:${userId}:${maxDepth}`;
    const cached = await this.cache.get(cacheKey);
    if (cached) return cached;
    
    const suggestions = new Map<number, number>(); // friend -> mutual count
    const visited = new Set<number>([userId]);
    const queue: Array<{ node: number; depth: number }> = [{ node: userId, depth: 0 }];
    
    while (queue.length > 0) {
      const { node, depth } = queue.shift()!;
      
      if (depth >= maxDepth) continue;
      
      // Get friends in batches
      const friends = await this.graph.getFriendsBatch(node, this.batchSize);
      
      for (const friend of friends) {
        if (visited.has(friend)) continue;
        
        if (depth === maxDepth - 1) {
          // Count mutual friends
          const mutualCount = await this.countMutualFriends(userId, friend);
          if (mutualCount > 0) {
            suggestions.set(friend, mutualCount);
          }
        } else {
          visited.add(friend);
          queue.push({ node: friend, depth: depth + 1 });
        }
      }
    }
    
    // Sort by mutual friends, return top N
    const sorted = Array.from(suggestions.entries())
      .sort((a, b) => b[1] - a[1])
      .slice(0, 10)
      .map(([friend]) => friend);
    
    await this.cache.set(cacheKey, sorted, 3600); // Cache for 1 hour
    return sorted;
  }
  
  // Parallel BFS for large graphs
  async parallelBFS(start: number, maxDepth: number): Promise<Map<number, number>> {
    const levels = new Map<number, number>();
    const visited = new Set<number>([start]);
    let currentLevel = new Set<number>([start]);
    levels.set(start, 0);
    
    for (let depth = 0; depth < maxDepth && currentLevel.size > 0; depth++) {
      // Process current level in parallel
      const nextLevelPromises = Array.from(currentLevel).map(async (node) => {
        const neighbors = await this.graph.getNeighbors(node);
        return neighbors.filter(n => !visited.has(n));
      });
      
      const nextLevelArrays = await Promise.all(nextLevelPromises);
      const nextLevel = new Set(nextLevelArrays.flat());
      
      // Mark visited and set levels
      for (const node of nextLevel) {
        visited.add(node);
        levels.set(node, depth + 1);
      }
      
      currentLevel = nextLevel;
    }
    
    return levels;
  }
  
  // Stream-based traversal for very large graphs
  async *traverseStreaming(start: number): AsyncGenerator<number> {
    const visited = new Set<number>();
    const queue: number[] = [start];
    visited.add(start);
    
    while (queue.length > 0) {
      const batch: number[] = [];
      
      // Process batch
      for (let i = 0; i < this.batchSize && queue.length > 0; i++) {
        batch.push(queue.shift()!);
      }
      
      // Yield batch
      for (const node of batch) {
        yield node;
      }
      
      // Get neighbors for batch in parallel
      const neighborPromises = batch.map(node => this.graph.getNeighbors(node));
      const neighborArrays = await Promise.all(neighborPromises);
      
      // Add unvisited neighbors
      for (const neighbors of neighborArrays) {
        for (const neighbor of neighbors) {
          if (!visited.has(neighbor)) {
            visited.add(neighbor);
            queue.push(neighbor);
          }
        }
      }
    }
  }
  
  private async countMutualFriends(user1: number, user2: number): Promise<number> {
    const [friends1, friends2] = await Promise.all([
      this.graph.getFriends(user1),
      this.graph.getFriends(user2)
    ]);
    
    const set1 = new Set(friends1);
    return friends2.filter(f => set1.has(f)).length;
  }
}

class DistributedGraph {
  async getNeighbors(node: number): Promise<number[]> {
    // Fetch from distributed storage
    // Could be database, cache, or other service
    return [];
  }
  
  async getFriendsBatch(node: number, batchSize: number): Promise<number[]> {
    // Get friends in batches to avoid loading all at once
    return [];
  }
  
  async getFriends(node: number): Promise<number[]> {
    return this.getNeighbors(node);
  }
}

Features:

1. Depth-limited BFS: Stop at certain depth for friend suggestions
2. Caching: Cache results to avoid recomputation
3. Batch processing: Process nodes in batches
4. Parallel processing: Process multiple nodes simultaneously
5. Streaming: Handle very large graphs incrementally
6. Mutual friend counting: Optimize friend suggestions

• DFS: Uses stack, explores depth-first, good for paths and cycles
• BFS: Uses queue, explores level-by-level, good for shortest paths
• Time complexity: O(V + E) for both
• Space complexity: O(V) for visited, O(V) stack/queue
• Cycle detection: Recursion stack for directed, parent for undirected
• Connected components: Check all unvisited nodes
• Applications: Path finding, cycle detection, connectivity, shortest paths