Graph Traversal

Depth-First Search

What is Depth-First Search?

Depth-First Search explores a graph by plunging as deep as possible down one path before ever backing up: from the current vertex, move to an unvisited neighbor, then from there to one of its unvisited neighbors, and so on — only backtracking to try a different branch once a path runs out of new vertices to reach. Unlike BFS's expanding rings, DFS traces out one long tendril at a time.

How Does It Work?

That behavior comes from using a stack (last-in, first-out) instead of a queue. Whichever vertex was discovered most recently is the one explored next, which is exactly what "keep going deeper" means — the newest neighbor found always jumps ahead of anything discovered earlier and still waiting. A stack can be explicit (an array used as a stack) or implicit, via the call stack of a recursive function — both produce the same traversal order.

A subtlety worth noting: with an explicit stack, a vertex can end up pushed more than once before it's actually processed, if two different vertices both discover it as a neighbor before it's popped. That's fine — a visited check happens when a vertex is popped, not when it's pushed, so any duplicate is simply skipped once it's already been handled. This is a real difference from BFS, which marks a vertex visited the moment it's enqueued specifically to prevent that kind of duplication.

DFS from A plunges down the B branch completely before ever trying C
A1B2D3E4C5visit order: A, B, D, E, C — one path fully explored before backtracking

Algorithm Steps

  1. Push the start vertex onto the stack
  2. While the stack isn't empty, repeat:
    • Pop a vertex; if it's already visited, skip it and continue
    • Otherwise, mark it visited and process it (this is the visit order)
    • Push each of its unvisited neighbors onto the stack
  3. Stop when the stack is empty — every vertex reachable from the start has been visited

Time Complexity

  • Time Complexity: O(V + E) — every vertex is popped and processed once, and every edge is examined once across the whole run.
  • Space Complexity: O(V) — for the stack (explicit or via recursion) and the visited set in the worst case.

Time Complexity Analysis

Advertisement

DFS is the natural tool whenever "is there a path at all" matters more than "what's the shortest path" — detecting cycles, finding connected components, topological sorting of a dependency graph, and solving maze- or puzzle-like search spaces where backtracking through one failed branch to try another is exactly the desired behavior.

Daily DSA Challenge by Scale Engineer

Watch Depth-First Search plunge down one path before backtracking

Build a graph, pick a start vertex, and run DFS

Graph

Add a vertex to begin
UnvisitedVisitedCurrently poppedEdge being explored

Test Your Knowledge before moving forward!

Depth-First Search Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Depth-First Search Implementation

// Recursive DFS: the call stack itself plays the role of the stack —
// each recursive call goes one level deeper before returning to try
// the next neighbor.
function dfs(adjList, start, visited = new Set(), order = []) {
  visited.add(start);
  order.push(start);

  for (const neighbor of adjList[start] || []) {
    if (!visited.has(neighbor)) {
      dfs(adjList, neighbor, visited, order);
    }
  }

  return order;
}

// Iterative version with an explicit stack. A vertex may be pushed more
// than once; the visited check happens when it's popped, not when it's
// pushed, so a duplicate pop is simply skipped.
function dfsIterative(adjList, start) {
  const visited = new Set();
  const stack = [start];
  const order = [];

  while (stack.length > 0) {
    const current = stack.pop();
    if (visited.has(current)) continue;

    visited.add(current);
    order.push(current);

    for (const neighbor of [...(adjList[current] || [])].reverse()) {
      if (!visited.has(neighbor)) stack.push(neighbor);
    }
  }

  return order;
}

// Usage example
const adjList = { A: ["B", "C"], B: ["A", "D"], C: ["A"], D: ["B"] };
dfs(adjList, "A"); // ["A", "B", "D", "C"]

Done With the Learning

Mark Depth-First Search as done and view it on your dashboard

Explore Other Topics

Breadth-First Search

Dijkstra's Algorithm

Adjacency List

Adjacency Matrix

Structure & Properties