Depth-First Search (DFS)

Depth-First Search is a graph traversal algorithm used to explore a graph or tree by visiting as far as possible along each branch before backtracking.

How DFS Works

1. Starting Point:

   • Begin at a starting node (usually the root in a tree or any arbitrary node in a graph).

2. Visit and Mark:

   • Visit the current node and mark it as visited to prevent revisiting.

3. Explore Neighbors:

   • Explore all unvisited neighbor nodes of the current node at the present depth level.
   • Recursively visit these neighbors to explore further depths.

4. Completion:

   • Continue this process until all nodes are visited or the goal is achieved.

Key Features

• Stack or Recursion: DFS uses a stack or recursion to explore nodes deeply.
• Memory Efficiency: In some cases, DFS uses less memory compared to BFS.

Efficiency

• Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges.
• Space Complexity: O(V) for maintaining the stack and visited nodes.

Advantages

• Good for pathfinding and topological sorting.
• Uses less memory in some cases compared to BFS.

Disadvantages

• May get stuck in very deep branches before finding the solution.
• Not guaranteed to find the shortest path.

Depth-First Search Implementation in JavaScript

Here's an example of Depth-First Search implemented in JavaScript:

function DFS(graph, currentNode, visited) {
    if (!visited.has(currentNode)) {
        // Process the current node
        console.log(currentNode);
        visited.add(currentNode);
        for (const neighbor of graph[currentNode]) {
            DFS(graph, neighbor, visited);
        }
    }
}
 
// Example usage
const graph = {
    A: ['B', 'C'],
    B: ['A', 'D', 'E'],
    C: ['A', 'F', 'G'],
    D: ['B'],
    E: ['B'],
    F: ['C'],
    G: ['C'],
};
 
const visited = new Set();
DFS(graph, 'A', visited); // Starting DFS from node 'A'