JavaScript: Depth-First Search (DFS) on a Graph

Introduction

Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. Starting from the root (or any arbitrary node in the graph), DFS explores as far as possible along each branch before backtracking. This algorithm is often used for pathfinding, maze solving, and topological sorting.

This guide will walk you through writing a JavaScript program to perform DFS on a graph represented using an adjacency list.

Problem Statement

Create a JavaScript program that:

• Implements Depth-First Search (DFS) on a graph.
• Traverses the graph and prints the nodes visited in DFS order.

Example:

• Input: Graph represented by an adjacency list:

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

• Starting Node: 'A'
• Output: A -> B -> D -> E -> F -> C

Solution Steps

1. Represent the Graph Using an Adjacency List: Use an object where keys represent the nodes and values represent the list of connected nodes.
2. Implement DFS:
   • Use a recursive approach.
   • Track the nodes that have already been visited to avoid cycles.
3. Display the Traversal: Output the nodes in the order they are visited by DFS.

JavaScript Program

DFS Implementation

// JavaScript Program to Perform Depth-First Search on a Graph
// Author: https://www.rameshfadatare.com/

// Step 1: Define the graph using an adjacency list
const graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
};

// Step 2: Define the DFS function
function dfs(node, visited = new Set()) {
    // Mark the current node as visited
    visited.add(node);
    console.log(node);

    // Step 3: Recur for all the vertices adjacent to this vertex
    for (const neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
            dfs(neighbor, visited);
        }
    }
}

// Step 4: Perform DFS starting from node 'A'
console.log("Depth-First Search Traversal starting from node 'A':");
dfs('A');

Explanation

Step 1: Represent the Graph as an Adjacency List

• The graph is represented as an object where each node is a key, and its value is an array of adjacent nodes (its neighbors).

Step 2: Define the DFS Function

• The dfs() function accepts a node to start from and a visited set to track visited nodes.
• The node is marked as visited by adding it to the visited set, and its value is printed to indicate it was visited.

Step 3: Recursively Visit Neighboring Nodes

• For each neighbor of the current node, if the neighbor has not been visited, the dfs() function is called recursively on the neighbor.

Step 4: Perform DFS Starting from Node 'A'

• The DFS traversal is initiated by calling dfs('A'), and the traversal starts from node 'A'.

Output Example

Depth-First Search Traversal starting from node 'A':
A
B
D
E
F
C

Example with Different Input

const graph = {
    '1': ['2', '3'],
    '2': ['4'],
    '3': ['5'],
    '4': ['6'],
    '5': ['6'],
    '6': []
};

console.log("Depth-First Search Traversal starting from node '1':");
dfs('1');

Output:

Depth-First Search Traversal starting from node '1':
1
2
4
6
3
5

Iterative DFS Using a Stack

Alternatively, DFS can be implemented iteratively using a stack, which mimics the recursive function call stack.

Iterative DFS Implementation

// JavaScript Program to Perform Iterative Depth-First Search on a Graph
// Author: https://www.rameshfadatare.com/

function iterativeDFS(startNode) {
    const visited = new Set();
    const stack = [startNode];

    console.log("Iterative DFS Traversal:");

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

        if (!visited.has(node)) {
            console.log(node);
            visited.add(node);

            // Add neighbors to the stack in reverse order to ensure correct traversal order
            for (const neighbor of graph[node].reverse()) {
                if (!visited.has(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }
}

// Example usage
iterativeDFS('A');

Output for Iterative DFS

Iterative DFS Traversal:
A
C
F
B
E
D

Conclusion

This JavaScript program demonstrates how to perform a Depth-First Search (DFS) on a graph using both recursive and iterative approaches. DFS is useful for exploring all possible paths in a graph and can be applied to various problems such as pathfinding, topological sorting, and solving mazes. Understanding both recursive and iterative implementations is essential for mastering graph traversal techniques.