Implementation of DFS Algorithm in JavaScript

Depth First Search (DFS) is a powerful tool for exploring graphs, and understanding how to implement it is key to solving many computer science problems. In this article, we’ll focus on how to write a DFS algorithm in JavaScript.

Tip

Before diving into the implementation, it’s helpful to have a good understanding of what graphs are and the basic idea behind Depth First Search. You can learn more about them in these articles:

Representing a Graph in JavaScript

Before we can implement DFS, we need a way to represent our graph in JavaScript. Two common ways to do this are using an adjacency list or an adjacency matrix.

Adjacency List

An adjacency list represents the graph as an object (like a dictionary) where each key is a node, and its value is an array of its neighboring nodes. This is efficient for sparse graphs (graphs with fewer connections).

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

Adjacency Matrix

An adjacency matrix represents the graph as a 2D array where matrix[i][j] = 1 if there’s an edge from vertex i to vertex j, and 0 otherwise. It’s simpler to implement but uses more memory, especially for sparse graphs.

// In this example, let's assume nodes are 0, 1, 2, 3, 4, 5, corresponding to A, B, C, D, E, F
// Matrix must be square (NxN) where N is the number of nodes
const matrix = [
    [0, 1, 1, 0, 0, 0],  // A
    [0, 0, 0, 1, 1, 0],  // B
    [0, 0, 0, 0, 0, 1],  // C
    [0, 0, 0, 0, 0, 0],  // D
    [0, 0, 0, 0, 0, 1],  // E
    [0, 0, 0, 0, 0, 0]   // F
];

In this article, we will focus on representing graphs using the adjacency list, as it’s often more efficient for DFS.

Recursive DFS Implementation

The most common and intuitive way to implement DFS is using recursion. Here’s how it works:

  1. Mark the current node as visited. We use an object called visited to keep track of visited nodes.
  2. Process the current node. This could involve printing the node’s value, adding it to an array, or performing any other action.
  3. Explore the neighbors. For each neighbor of the current node:
    • If the neighbor hasn’t been visited yet, recursively call the DFS function on that neighbor.

Here’s the JavaScript code for the recursive DFS:

function dfsRecursive(graph, node, visited = {}) {
  if (!visited[node]) {
    visited[node] = true;
    console.log(node); // Process the node (e.g., print it)

    const neighbors = graph[node];
    if (neighbors) {
      for (const neighbor of neighbors) {
        dfsRecursive(graph, neighbor, visited);
      }
    }
  }
}

Here’s how you might use this function:

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

console.log("DFS Traversal (Recursive):");
dfsRecursive(graph, 'A');  // Start DFS from node 'A'
console.log();  // Add a newline for clarity
// Expected output (order may vary depending on neighbor order in the dict):
// DFS Traversal (Recursive):
// A
// B
// D
// E
// F
// C
  • The function dfsRecursive takes the graph, the current node, and a visited object as input.
  • If visited is not provided in the initial call, we create an empty object to store visited nodes.
  • We check if the current node is in the visited object. If it’s not, we add it to the object and process it (in this case, print it).
  • Then, we iterate through the neighbors of the current node and recursively call dfsRecursive for each unvisited neighbor.

Iterative DFS Implementation using a Stack

An alternative to recursion is to use an iterative approach with a stack. This can be helpful to avoid recursion depth limits.

Here’s the iterative approach:

  1. Create a stack and add the starting node to it.
  2. Create an object to keep track of visited nodes.
  3. While the stack is not empty:
    • Pop a node from the stack.
    • If the node hasn’t been visited:
      • Mark it as visited.
      • Process the node (e.g., print it).
      • Add all its unvisited neighbors to the stack.

Here’s the JavaScript code for the iterative DFS:

function dfsIterative(graph, startNode) {
  const visited = {};  // Keep track of visited nodes
  const stack = [startNode];  // Use an array as a stack

  console.log("DFS Traversal (Iterative):");
  while (stack.length > 0) {
    const node = stack.pop();  // Pop the top node

    if (!visited[node]) {
      visited[node] = true;
      console.log(node);  // Process the node

      // Add neighbors to the stack in reverse order to maintain DFS order
      const neighbors = graph[node];
      if (neighbors) {
        for (let i = neighbors.length - 1; i >= 0; i--) {
          const neighbor = neighbors[i];
          if (!visited[neighbor]) {
            stack.push(neighbor);
          }
        }
      }
    }
  }
  console.log();  // Add a newline for clarity
}

Here’s how you might use this function:

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

dfsIterative(graph, 'A');
// Possible output (order might differ slightly from recursive):
// DFS Traversal (Iterative):
// A
// C
// F
// B
// E
// D
  • We initialize a visited object and a stack.
  • We push the startNode onto the stack.
  • The while loop continues as long as there are nodes in the stack.
  • Inside the loop, we pop a node from the stack. This is the node we’ll explore next.
  • If the node hasn’t been visited, we mark it as visited and process it.
  • We find all neighbors of the current node. For each neighbor that hasn’t been visited yet, we push it to the stack.
  • Note that we are iterating the neighbors in reversed order so that the visit sequence match closer to the recursive version of DFS.

Choosing Between Recursive and Iterative

  • Recursive DFS: Is often simpler to write and understand, closely matching the definition of DFS. However, it can lead to a stack overflow error if the graph is very deep.
  • Iterative DFS: Is more robust against deep graphs, as it uses heap memory for the stack. The logic might feel slightly less direct than recursion.

Both implementations have a time complexity of O(V + E), where V is the number of vertices (nodes) and E is the number of edges. The space complexity is O(V) in the worst case, as we need to store all vertices in the visited set and the stack (in the iterative version) or the call stack (in the recursive version). You can refer to this article to dive deeper into the time and space complexity of DFS.

What’s Next?

Now that you’ve learned how to implement DFS in JavaScript, you can explore other related articles: