Depth First Search for Graphs in JavaScript

Introduction to Graph Traversal #

Depth First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. Unlike tree traversal where we have a clear hierarchical structure with left and right children, graphs present unique challenges: they can contain cycles, have multiple paths between nodes, and lack a defined root. This makes DFS for graphs both more complex and more versatile than its tree-based counterpart.

In this comprehensive guide, we’ll explore how to implement DFS for graphs in JavaScript, understand the underlying strategy, examine common pitfalls, and look at practical applications.

Understanding the Core Strategy #

The DFS algorithm for graphs follows a systematic approach that differs from tree traversal in one critical aspect: cycle detection and visited node tracking. Without this mechanism, we could traverse the same nodes infinitely, getting stuck in cycles.

The Algorithm Steps #

Initialize: Start with a node and add it to a stack (Last In, First Out data structure)
Pop: Remove the top element from the stack
Process: Perform whatever operation is needed on the current node (printing, collecting, validating, etc.)
Explore: For each neighbor of the current node:
- Check if the neighbor has been visited
- If not visited, mark it as visited and add it to the stack
Repeat: Continue until the stack is empty

Why Use a Stack? #

The stack is the heart of DFS. By using a Last In, First Out (LIFO) structure, we ensure that we explore deeply before exploring broadly. The most recently discovered node is processed first, leading us down a single path before we backtrack.

Implementation in JavaScript #

Let’s build a robust implementation of DFS for graphs. We’ll start with the basic version and then explore variations.

Basic DFS Implementation #

function depthFirstSearch(graph, startNode) {
  // Initialize our data structures
  const stack = [startNode];
  const visited = new Set(); // Using Set for O(1) lookup
  const result = [];

  while (stack.length > 0) {
    // Remove from top of stack
    const current = stack.pop();

    // Skip if already visited (handles the case where neighbors add duplicates)
    if (visited.has(current)) {
      continue;
    }

    // Mark as visited and process the node
    visited.add(current);
    result.push(current);

    // Add all unvisited neighbors to stack
    // Note: We reverse to maintain left-to-right order (optional)
    const neighbors = graph[current] || [];
    for (let i = neighbors.length - 1; i >= 0; i--) {
      if (!visited.has(neighbors[i])) {
        stack.push(neighbors[i]);
      }
    }
  }

  return result;
}

Adjacency List Representation #

Graphs are typically represented as adjacency lists in JavaScript. Here’s how to set up a graph:

// Directed graph representation
const graph = {
  'A': ['B', 'C'],
  'B': ['D', 'E'],
  'C': ['F'],
  'D': [],
  'E': ['F'],
  'F': []
};

// Usage
const traversalOrder = depthFirstSearch(graph, 'A');
console.log('DFS Traversal:', traversalOrder);
// Output: ['A', 'B', 'D', 'E', 'F', 'C']

Adjacency Matrix Implementation #

For adjacency matrices (useful for dense graphs), we need a slightly different approach:

function dfsMatrix(adjMatrix, startNode) {
  const n = adjMatrix.length;
  const stack = [startNode];
  const visited = new Array(n).fill(false);
  const result = [];

  while (stack.length > 0) {
    const current = stack.pop();

    if (visited[current]) {
      continue;
    }

    visited[current] = true;
    result.push(current);

    // Check all possible neighbors (matrix indices)
    for (let neighbor = n - 1; neighbor >= 0; neighbor--) {
      if (adjMatrix[current][neighbor] === 1 && !visited[neighbor]) {
        stack.push(neighbor);
      }
    }
  }

  return result;
}

// Example with adjacency matrix
const adjMatrix = [
  [0, 1, 1, 0],  // Node 0 connects to 1, 2
  [0, 0, 0, 1],  // Node 1 connects to 3
  [0, 0, 0, 1],  // Node 2 connects to 3
  [0, 0, 0, 0]   // Node 3 has no outgoing edges
];

console.log('Matrix DFS:', dfsMatrix(adjMatrix, 0));
// Output: [0, 1, 3, 2]

Recursive Implementation #

While the iterative approach using a stack is more explicit, DFS can also be implemented recursively. The call stack acts as our implicit stack:

function dfsRecursive(graph, startNode, visited = new Set(), result = []) {
  // Base case: if already visited, return
  if (visited.has(startNode)) {
    return result;
  }

  // Mark as visited and process
  visited.add(startNode);
  result.push(startNode);

  // Recursively visit all neighbors
  const neighbors = graph[startNode] || [];
  for (const neighbor of neighbors) {
    dfsRecursive(graph, neighbor, visited, result);
  }

  return result;
}

// Usage
const graph = {
  'A': ['B', 'C'],
  'B': ['D', 'E'],
  'C': ['F'],
  'D': [],
  'E': ['F'],
  'F': []
};

console.log('Recursive DFS:', dfsRecursive(graph, 'A'));

Common Pitfalls and How to Avoid Them #

Pitfall 1: Not Checking for Visited Nodes #

The original code had a critical bug:

// INCORRECT - This will cause infinite loops
if (!visited[current]) {
  visited.push(current);
  stack.push(current);
}

The issue here is checking visited[current] on the neighbors, but then pushing current instead of the neighbor. The correct version:

// CORRECT
for (const neighbor of neighbors) {
  if (!visited.has(neighbor)) {
    stack.push(neighbor);
  }
}

Pitfall 2: Using Array Instead of Set for Visited Tracking #

Arrays require O(n) lookup time with includes(), while Sets provide O(1) lookup. For large graphs, this difference is significant:

// Slower - O(n) lookup
const visited = [];
if (!visited.includes(node)) { ... }

// Faster - O(1) lookup
const visited = new Set();
if (!visited.has(node)) { ... }

Pitfall 3: Not Handling Disconnected Graphs #

A single DFS only explores nodes reachable from the starting node. For disconnected graphs, you need to run DFS from multiple starting points:

function dfsComplete(graph) {
  const visited = new Set();
  const result = [];

  for (const node in graph) {
    if (!visited.has(node)) {
      dfsFromNode(graph, node, visited, result);
    }
  }

  return result;
}

function dfsFromNode(graph, startNode, visited, result) {
  const stack = [startNode];

  while (stack.length > 0) {
    const current = stack.pop();

    if (visited.has(current)) continue;

    visited.add(current);
    result.push(current);

    const neighbors = graph[current] || [];
    for (let i = neighbors.length - 1; i >= 0; i--) {
      if (!visited.has(neighbors[i])) {
        stack.push(neighbors[i]);
      }
    }
  }
}

Practical Applications #

1. Cycle Detection #

DFS can detect cycles in directed graphs by tracking nodes in the current path:

function hasCycle(graph) {
  const visited = new Set();
  const recursionStack = new Set();

  function dfs(node) {
    visited.add(node);
    recursionStack.add(node);

    const neighbors = graph[node] || [];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor)) return true;
      } else if (recursionStack.has(neighbor)) {
        return true; // Cycle detected
      }
    }

    recursionStack.delete(node);
    return false;
  }

  for (const node in graph) {
    if (!visited.has(node)) {
      if (dfs(node)) return true;
    }
  }

  return false;
}

2. Topological Sorting #

DFS is used in topological sorting of Directed Acyclic Graphs (DAGs):

function topologicalSort(graph) {
  const visited = new Set();
  const stack = [];

  function dfs(node) {
    visited.add(node);

    const neighbors = graph[node] || [];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        dfs(neighbor);
      }
    }

    stack.push(node); // Add to result after exploring all neighbors
  }

  for (const node in graph) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }

  return stack.reverse();
}

3. Path Finding #

Finding a path between two nodes:

function findPath(graph, start, end) {
  const stack = [[start, [start]]]; // [node, path]
  const visited = new Set();

  while (stack.length > 0) {
    const [current, path] = stack.pop();

    if (current === end) {
      return path;
    }

    if (visited.has(current)) continue;
    visited.add(current);

    const neighbors = graph[current] || [];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        stack.push([neighbor, [...path, neighbor]]);
      }
    }
  }

  return null; // No path found
}

Performance Analysis #

Time Complexity #

DFS visits each vertex once and explores each edge once, giving us:

Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges
For adjacency matrix: O(V²) since we must check all possible edges

Space Complexity #

Space Complexity: O(V) for the visited set and stack in worst case (linear graph)
Recursive implementation: O(h) where h is the maximum depth (call stack space)

Comparison: DFS vs BFS #

Aspect	DFS	BFS
Data Structure	Stack	Queue
Memory	Better for deep graphs	Better for shallow graphs
Path	May not find shortest	Finds shortest path
Use Cases	Topological sort, cycle detection	Shortest path, level-order

Conclusion #

Depth First Search is a powerful algorithm for graph traversal with numerous practical applications. The key differences from tree DFS are the need for visited node tracking and handling various graph representations. By understanding the core principles and common pitfalls, you can effectively implement DFS for solving complex graph problems.

Remember these key points:

Always track visited nodes to avoid infinite loops
Use Sets for O(1) lookup performance
Choose between iterative (explicit stack) and recursive implementations based on your needs
Consider disconnected graphs in your implementation
Understand the trade-offs between DFS and BFS for your specific use case

With these fundamentals mastered, you’re well-equipped to tackle advanced graph algorithms and solve real-world problems involving networks, dependencies, and complex relationships.