Depth-First Search

Category: Classical
Difficulty: Intermediate
Time Complexity: O(V + E)
Space Complexity: O(V)

Overview

DFS explores a graph by following each branch as far as possible before backtracking. It uses a stack (explicit or via recursion) and is useful for cycle detection, topological sorting, and finding connected components. DFS does NOT guarantee shortest paths.

Try It

Web: Open in Eigenvue →
Python:
```
import eigenvue
eigenvue.show("dfs")
```

Default Inputs

{
  "adjacencyList": {
    "A": [
      "B",
      "C"
    ],
    "B": [
      "A",
      "D",
      "E"
    ],
    "C": [
      "A",
      "F"
    ],
    "D": [
      "B"
    ],
    "E": [
      "B",
      "F"
    ],
    "F": [
      "C",
      "E"
    ]
  },
  "positions": {
    "A": {
      "x": 0.1,
      "y": 0.5
    },
    "B": {
      "x": 0.35,
      "y": 0.2
    },
    "C": {
      "x": 0.35,
      "y": 0.8
    },
    "D": {
      "x": 0.65,
      "y": 0.1
    },
    "E": {
      "x": 0.65,
      "y": 0.5
    },
    "F": {
      "x": 0.9,
      "y": 0.8
    }
  },
  "startNode": "A",
  "targetNode": "F"
}

Input Examples

6-node graph

{
  "adjacencyList": {
    "A": [
      "B",
      "C"
    ],
    "B": [
      "A",
      "D",
      "E"
    ],
    "C": [
      "A",
      "F"
    ],
    "D": [
      "B"
    ],
    "E": [
      "B",
      "F"
    ],
    "F": [
      "C",
      "E"
    ]
  },
  "positions": {
    "A": {
      "x": 0.1,
      "y": 0.5
    },
    "B": {
      "x": 0.35,
      "y": 0.2
    },
    "C": {
      "x": 0.35,
      "y": 0.8
    },
    "D": {
      "x": 0.65,
      "y": 0.1
    },
    "E": {
      "x": 0.65,
      "y": 0.5
    },
    "F": {
      "x": 0.9,
      "y": 0.8
    }
  },
  "startNode": "A",
  "targetNode": "F"
}

Linear chain

{
  "adjacencyList": {
    "A": [
      "B"
    ],
    "B": [
      "A",
      "C"
    ],
    "C": [
      "B",
      "D"
    ],
    "D": [
      "C"
    ]
  },
  "positions": {
    "A": {
      "x": 0.1,
      "y": 0.5
    },
    "B": {
      "x": 0.35,
      "y": 0.5
    },
    "C": {
      "x": 0.65,
      "y": 0.5
    },
    "D": {
      "x": 0.9,
      "y": 0.5
    }
  },
  "startNode": "A",
  "targetNode": "D"
}

Code

Pseudocode

function DFS(graph, start, target?):
  stack = [start]
  predecessor[start] = null
  visited = {}
  while stack is not empty:
    current = stack.pop()
    if current in visited: continue
    visited.add(current)
    if current == target:
      return reconstructPath(predecessor, target)
    for each neighbor of current (reversed):
      if neighbor not in visited:
        predecessor[neighbor] = current
        stack.push(neighbor)
  return null  // target not found

Python

def dfs(graph, start, target=None):
    stack = [start]
    visited = set()
    pred = {start: None}
    while stack:
        current = stack.pop()
        if current in visited:
            continue
        visited.add(current)
        if current == target:
            return reconstruct(pred, target)
        for neighbor in reversed(sorted(graph[current])):
            if neighbor not in visited:
                if neighbor not in pred:
                    pred[neighbor] = current
                stack.append(neighbor)
    return None

Key Concepts

Stack-Based Exploration

DFS uses a LIFO stack. The last node pushed is the first explored, causing the algorithm to go deep before wide.

Backtracking

When DFS reaches a dead end (no unvisited neighbors), it backtracks by popping the stack until it finds a node with unexplored neighbors.

Does NOT Find Shortest Paths

DFS may find a path to the target, but it is not guaranteed to be the shortest. Use BFS for shortest paths in unweighted graphs.

Common Pitfalls

Not shortest path: DFS can find a valid path but not the shortest one. The path depends on traversal order.
Infinite loops without visited check: In graphs with cycles, DFS will loop forever without a visited set.

Quiz

Q1: What data structure does DFS use?

A) Queue
B) Stack
C) Priority Queue
D) Array

Show answer

Answer: B) Stack

DFS uses a LIFO stack (or recursion, which implicitly uses the call stack).

Q2: Does DFS guarantee shortest paths?

A) Yes
B) No