Depth-First Search (DFS) Algorithm

What is DFS?

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It can be implemented using recursion or an explicit stack.

DFS Algorithm:

1. Start from the root (or any arbitrary node).
2. Mark the node as visited.
3. Explore each adjacent unvisited node recursively.
4. Backtrack when no more unvisited nodes are found.

Example:

Let's consider a simple graph:      A     /   \   B        C /   \           \ D   E          F

Adjacency List Representation:

const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B"],
  E: ["B"],
  F: ["C"]
};

Output:

A B D E C F

Complexity Analysis

Time Complexity:

O(V + E) where V is the number of vertices and E is the number of edges.

Space Complexity:

O(V) for storing visited nodes in recursion.

Use Cases of DFS:

• Pathfinding algorithms (e.g., Maze solving)
• Detecting cycles in graphs
• Topological sorting
• Connected components in a graph