# 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.

3. Apply our DFS on a sample graph.

# 3. Code Program

``````class Graph {
constructor() {
}

// Add a vertex to the graph
}

// Connect two vertices with an edge
}

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

(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
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();

// Connect vertices

// 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.

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.