Depth-First Search (DFS) Algorithm

DFS goes deep before going wide. It picks a direction and follows it as far as possible. When it hits a dead end, it backtracks and tries the next path.

Think of exploring a maze. You follow one corridor to the end before turning back to try another.

What It Does

DFS traverses a graph by exploring each branch fully before moving to the next. It uses a stack (or recursion, which is an implicit stack).

The Code

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }

  dfs(start) {
    const visited = new Set();
    const result = [];

    const traverse = (vertex) => {
      visited.add(vertex);
      result.push(vertex);

      for (const neighbor of this.adjacencyList[vertex]) {
        if (!visited.has(neighbor)) {
          traverse(neighbor);
        }
      }
    };

    traverse(start);
    return result;
  }
}

const g = new Graph();
['A', 'B', 'C', 'D', 'E', 'F'].forEach(v => g.addVertex(v));
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.addEdge('C', 'E');
g.addEdge('D', 'E');
g.addEdge('D', 'F');

console.log(g.dfs('A'));
// ['A', 'B', 'D', 'E', 'C', 'F']

How It Works

Starting from A:

1. Visit A → go to B (first neighbor).
2. Visit B → go to D.
3. Visit D → go to E.
4. Visit E → C is unvisited, go to C.
5. C's neighbors are all visited. Backtrack.
6. Back to D → visit F.
7. Stack is empty. Done.

Complexity

• Time: O(V + E) — visit every vertex, check every edge.
• Space: O(V) — the recursion stack can go as deep as the number of vertices.

DFS vs BFS

When to Use DFS

• Cycle detection — if you visit a node that's already on the current path, there's a cycle.
• Topological sorting — process dependencies in order.
• Solving puzzles — mazes, Sudoku, N-Queens.
• Connected components — find all nodes reachable from a start.

The Trade-off

DFS uses less memory than BFS on wide graphs. But it doesn't find shortest paths. And on very deep graphs (or infinite graphs), DFS can get stuck. BFS is safer when you care about distance.