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

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

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

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