DSA Lesson 20 of 33

Depth First Search

Learn how DFS explores a graph deeply before backtracking.

Course Progress61%

Theory

Depth First Search, or DFS, explores one path as deeply as possible before backtracking. It can be implemented using recursion or an explicit stack. DFS is useful in graph traversal, cycle detection and many backtracking problems.

Example

function dfs(graph, node, visited = new Set()) { if (visited.has(node)) return; visited.add(node); for (const next of graph[node]) { dfs(graph, next, visited); } } const graph = { A: ["B", "C"], B: ["D"], C: [], D: [] }; dfs(graph, "A");

Expected Output

All reachable nodes are visited using depth-first traversal.

Practice

Implement DFS using both recursion and a stack.

Interview Questions

  1. What is DFS?
  2. Which data structure can DFS use?
  3. What is the difference between BFS and DFS?
  4. Where is DFS useful?