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

// Adjacency List (most common)
class Graph {
  private adjList: Map<number, number[]>;
  
  constructor() {
    this.adjList = new Map();
  }
  
  addVertex(v: number): void {
    if (!this.adjList.has(v)) {
      this.adjList.set(v, []);
    }
  }
  
  addEdge(v: number, w: number): void {
    this.adjList.get(v)!.push(w);
    // For undirected: this.adjList.get(w)!.push(v);
  }
  
  getNeighbors(v: number): number[] {
    return this.adjList.get(v) || [];
  }
}

// Adjacency Matrix
class GraphMatrix {
  private matrix: number[][];
  private size: number;
  
  constructor(size: number) {
    this.size = size;
    this.matrix = Array(size).fill(null).map(() => Array(size).fill(0));
  }
  
  addEdge(v: number, w: number): void {
    this.matrix[v][w] = 1;
    // For undirected: this.matrix[w][v] = 1;
  }
  
  hasEdge(v: number, w: number): boolean {
    return this.matrix[v][w] === 1;
  }
}

Depth-First Search (DFS)

Recursive:

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

// Time: O(V + E) where V = vertices, E = edges
// Space: O(V) for visited set + O(V) recursion stack

Iterative:

function dfsIterative(graph: Map<number, number[]>, start: number): number[] {
  const result: number[] = [];
  const visited = new Set<number>();
  const stack: number[] = [start];
  
  while (stack.length > 0) {
    const node = stack.pop()!;
    
    if (visited.has(node)) continue;
    
    visited.add(node);
    result.push(node);
    
    // Push neighbors (reverse order for same result as recursive)
    const neighbors = graph.get(node) || [];
    for (let i = neighbors.length - 1; i >= 0; i--) {
      if (!visited.has(neighbors[i])) {
        stack.push(neighbors[i]);
      }
    }
  }
  
  return result;
}

// Time: O(V + E)
// Space: O(V)

Breadth-First Search (BFS)

function bfs(graph: Map<number, number[]>, start: number): number[] {
  const result: number[] = [];
  const visited = new Set<number>();
  const queue: number[] = [start];
  visited.add(start);
  
  while (queue.length > 0) {
    const node = queue.shift()!;
    result.push(node);
    
    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  
  return result;
}

// Time: O(V + E)
// Space: O(V) for queue

BFS with Level Information

function bfsLevels(graph: Map<number, number[]>, start: number): number[][] {
  const levels: number[][] = [];
  const visited = new Set<number>();
  const queue: number[] = [start];
  visited.add(start);
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    const level: number[] = [];
    
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      level.push(node);
      
      for (const neighbor of graph.get(node) || []) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
    
    levels.push(level);
  }
  
  return levels;
}

---

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:

Feature	DFS	BFS
Data structure	Stack	Queue
Order	Depth-first	Level-by-level
Shortest path	No guarantee	Guaranteed (unweighted)
Space	O(h) height	O(w) width
Implementation	Recursive/iterative	Usually iterative

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

---

Key Takeaways

• 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