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

1. Introduction

The Depth-First Search (DFS) is a fundamental algorithm for traversing or searching tree or graph data structures. The algorithm commences at the root node and delves as far as possible down a branch before backtracking. In this guide, we will learn how to implement Depth-First Search (DFS) on a graph using JavaScript.

2. Program Overview

1. Set up the Graph class.

2. Integrate core methods: addVertex, addEdge, and dfs.

3. Apply our DFS on a sample graph.

3. Code Program

class Graph {
    constructor() {
        this.adjacencyList = {}; // Store vertices and their adjacent nodes
    }

    // Add a vertex to the graph
    addVertex(vertex) {
        if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }

    // Connect two vertices with an edge
    addEdge(vertex1, vertex2) {
        this.adjacencyList[vertex1].push(vertex2);
        this.adjacencyList[vertex2].push(vertex1);
    }

    // DFS traversal using recursion
    dfs(start) {
        const result = [];      // List to store the result of DFS traversal
        const visited = {};     // Object to store visited vertices
        const adjacencyList = this.adjacencyList;

        (function dfsRecursion(vertex) {
            if (!vertex) return null;  // Base case if vertex is not valid
            visited[vertex] = true;    // Mark the vertex as visited
            result.push(vertex);       // Push vertex to the result list
            adjacencyList[vertex].forEach(neighbor => { // Visit adjacent vertices
                if (!visited[neighbor]) {
                    return dfsRecursion(neighbor);  // Recurse on the adjacent vertex
                }
            });
        })(start);  // Immediately invoked function expression to kickstart the DFS
        
        return result;
    }
}

// Create a new graph
const graph = new Graph();

// Add vertices
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');

// Connect vertices
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');

// Perform DFS from vertex A
console.log(graph.dfs('A'));

Output:

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

4. Step By Step Explanation

1. Initialization: We initiate our graph with an adjacency list to represent vertices and their connections.

2. addVertex Method: This enables the addition of a vertex to our graph. We simply use the vertex as a key and initialize its value as an empty array to store connections.

3. addEdge Method: This function is responsible for linking two vertices together. Both vertices are added to each other's adjacency list.

4. DFS Algorithm:

- We commence the traversal at the specified starting vertex.

- Every vertex we visit is marked as "visited" and appended to the result list.

- For each neighboring vertex, if it has not been visited, we execute the DFS on it. This is performed recursively, which inherently uses the call stack to backtrack to previous vertices.

5. Sample Graph: The constructed graph has 6 vertices (A to F). DFS is initiated from vertex A which then explores as deeply as possible along each branch before backtracking.

The order in the result list showcases the path that DFS takes, illustrating the depth-first nature of the traversal. 

The DFS algorithm provides valuable insights into the structure of graphs, and this JavaScript implementation offers a foundational starting point for deeper exploration of graph algorithms.