Depth-First Search Algorithm in JavaScript: Explained with Code Snippet and Example

The Depth-First Search (DFS) algorithm is widely used for traversing or exploring graph and tree data structures. It starts at a specific node and continues exploring as far as possible along each branch before backtracking. In this article, we will delve into the implementation of the Depth-First Search algorithm in JavaScript, along with a code snippet and an illustrative example.

Understanding Depth-First Search Algorithm

The DFS algorithm follows a straightforward principle: Visit a node, mark it as visited, and recursively visit its adjacent unvisited nodes. This process continues until no unvisited nodes remain. The algorithm can be implemented using recursion or a stack data structure.

JavaScript Code Snippet for Depth-First Search Algorithm

Let's examine a JavaScript code snippet that implements the Depth-First Search algorithm:

class Graph {

  constructor() {

    this.adjacencyList = {};

  }

  addVertex(vertex) {

    if (!this.adjacencyList[vertex]) {

      this.adjacencyList[vertex] = [];

    }

  }

  addEdge(vertex1, vertex2) {

    this.adjacencyList[vertex1].push(vertex2);

    this.adjacencyList[vertex2].push(vertex1);

  }

  depthFirstSearch(startingVertex) {

    const visited = {};

    const result = [];

    const dfs = (vertex) => {

      if (!vertex) return;

      visited[vertex] = true;

      result.push(vertex);

      this.adjacencyList[vertex].forEach((neighbor) => {

        if (!visited[neighbor]) {

          dfs(neighbor);

        }

      });

    };

    dfs(startingVertex);

    return result;

  }

}

// Example usage

const graph = new Graph();

graph.addVertex('A');

graph.addVertex('B');

graph.addVertex('C');

graph.addVertex('D');

graph.addVertex('E');

graph.addVertex('F');

graph.addEdge('A', 'B');

graph.addEdge('A', 'C');

graph.addEdge('B', 'D');

graph.addEdge('C', 'E');

graph.addEdge('D', 'E');

graph.addEdge('D', 'F');

graph.addEdge('E', 'F');

console.log(graph.depthFirstSearch('A'));

Explanation of the Code Snippet

- We begin by creating a `Graph` class with an `adjacencyList` property to store the vertices and their corresponding connections.

- The `addVertex` method adds a new vertex to the adjacency list if it doesn't already exist.

- The `addEdge` method establishes an edge between two vertices by adding them to each other's adjacency lists.

- The `depthFirstSearch` method performs the actual Depth-First Search. It takes a starting vertex as a parameter, initializes an empty `visited` object to keep track of visited vertices and an empty `result` array to store the traversal order.

- Inside the `dfs` helper function, we mark the current vertex as visited, add it to the result array, and recursively call `dfs` on its unvisited neighbors.

- Finally, we invoke the `depthFirstSearch` method on a sample graph, starting from vertex 'A', and log the result to the console.

Example Usage of Depth-First Search Algorithm

In our example, we have a graph with six vertices (A, B, C, D, E, F) and several edges connecting them. We initiate the Depth-First Search from vertex 'A' using the `depthFirstSearch` method and log the result to the console.

The output of the example will be:

[ 'A', 'B', 'D', 'E', 'C', 'F' ]

This represents the order in which the vertices were traversed during the Depth-First Search. Starting from vertex 'A', the algorithm explores all possible paths, visiting each vertex and its neighbors until no unvisited vertices are left.

Conclusion

The Depth-First Search algorithm is a fundamental technique for traversing graphs or trees. In this article, we provided a JavaScript implementation of the Depth-First Search algorithm, explained the code snippet in detail, and demonstrated its usage with an example graph. By understanding and utilizing this algorithm, you can efficiently explore and analyze graph-based data structures in your JavaScript projects.