prep4place
Back to Visualizer

Depth-First Search (DFS)

DFS explores a graph by going as deep as possible along each branch before backtracking. Uses recursion or a stack data structure.

O(V + E)Uses Stack/Recursion
Speed:
Start
Current
Backtracking
Visited

Current Stack (Call Stack)

Empty

Visit Order

Start the visualization

How DFS Works

  1. 1Start from the source node
  2. 2Mark current node as visited
  3. 3Explore first unvisited neighbor (go deep)
  4. 4Recursively apply DFS to that neighbor
  5. 5Backtrack when no unvisited neighbors
  6. 6Continue until all reachable nodes visited
  7. 7DFS explores as deep as possible first

DFS vs BFS

  • • DFS uses Stack, BFS uses Queue
  • • DFS goes deep, BFS goes wide
  • • DFS uses less memory for sparse graphs
  • • BFS finds shortest path, DFS finds any path

Complexity

TimeO(V + E)
SpaceO(V)

Code

function dfs(graph, start) {
  const visited = new Set();
  const result = [];
  
  function explore(node) {
    if (visited.has(node)) return;
    
    visited.add(node);
    result.push(node);
    
    for (const neighbor of graph[node]) {
      explore(neighbor);
    }
  }
  
  explore(start);
  return result;
}

// Iterative version with stack:
function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];
  const result = [];
  
  while (stack.length > 0) {
    const node = stack.pop();
    if (!visited.has(node)) {
      visited.add(node);
      result.push(node);
      // Add neighbors in reverse order
      for (const n of graph[node].reverse()) {
        stack.push(n);
      }
    }
  }
  return result;
}