Depth-First Search (DFS) explores a graph by going as deep as possible before returning.

Its biggest advantage is:

DFS naturally handles graph traversal, connected components, path exploration, cycle detection, grids, and backtracking.

Focus on recognizing:

“Explore deeply” + “Visit neighbors recursively” = DFS

Pattern Table

Pattern	Typical Questions	Trigger
Basic DFS	Graph traversal	Visit every reachable node
Connected Components	Count groups	Disconnected graph
Path Finding	Does a route exist?	Search until target
Cycle Detection	Detect loops	Parent / recursion-state tracking
Grid DFS	Islands / regions	Matrix traversal
Backtracking DFS	Generate possibilities	Choose → Recurse → Undo

Mental Trigger

Recursive Exploration + Deep Traversal → DFS

For backtracking problems:

Choose → Recurse → Undo → Try next choice

1. Generic DFS Template (Base)

This is the main graph DFS template to remember.

Same graph as the BFS example — watch DFS snake deep instead of spreading level by level:

Depth-First Search

Dive deep before backtracking; explores one branch fully.

Mark a node visited, then recursively dive into each unvisited neighbour. The call stack is the path; when a branch dead-ends you unwind and the next neighbour is explored. Order is a deep snake vs BFS's rings.

GRAPH VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dfs(node):
                      
                        2
                          visited.add(node)
                      
                        3
                          for each neighbour of node:
                      
                        4
                            if neighbour not visited:
                      
                        5
                              dfs(neighbour)   // dive deep first

public void dfs(
        List<List<Integer>> graph,
        int node,
        boolean[] visited) {

    visited[node] = true;

    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited);
        }
    }
}

def dfs(graph, node, visited):
    visited[node] = True

    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)

void dfs(vector<vector<int>>& graph,
         int node,
         vector<bool>& visited) {

    visited[node] = true;

    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited);
        }
    }
}

function dfs(graph, node, visited) {
  visited[node] = true;

  for (const neighbor of graph[node]) {
    if (!visited[neighbor]) {
      dfs(graph, neighbor, visited);
    }
  }
}

Everything else in graph DFS is a modification of this template.

Pattern 1: Basic DFS Traversal

Code

public List<Integer> dfsTraversal(
        List<List<Integer>> graph,
        int start) {

    boolean[] visited = new boolean[graph.size()];
    List<Integer> order = new ArrayList<>();

    dfs(graph, start, visited, order);

    return order;
}

private void dfs(
        List<List<Integer>> graph,
        int node,
        boolean[] visited,
        List<Integer> order) {

    visited[node] = true;
    order.add(node);

    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited, order);
        }
    }
}

def dfs_traversal(graph, start):
    visited = [False] * len(graph)
    order = []

    def dfs(node):
        visited[node] = True
        order.append(node)

        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)

    dfs(start)
    return order

void dfs(vector<vector<int>>& graph,
         int node,
         vector<bool>& visited,
         vector<int>& order) {

    visited[node] = true;
    order.push_back(node);

    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited, order);
        }
    }
}

vector<int> dfsTraversal(vector<vector<int>>& graph,
                         int start) {
    vector<bool> visited(graph.size(), false);
    vector<int> order;

    dfs(graph, start, visited, order);

    return order;
}

function dfsTraversal(graph, start) {
  const visited = new Array(graph.length).fill(false);
  const order = [];

  function dfs(node) {
    visited[node] = true;
    order.push(node);

    for (const neighbor of graph[node]) {
      if (!visited[neighbor]) {
        dfs(neighbor);
      }
    }
  }

  dfs(start);
  return order;
}

What Changed from the Base Template?

Added traversal storage

Base:

// Nothing stored

Changed:

List<Integer> order = new ArrayList<>();

because we need to return the traversal order.

Record each visited node

Added:

order.add(node);

because each node should appear in the result.

Basic Traversal = Base DFS + Store node order.

Pattern 2: Connected Components

Code

public int countComponents(List<List<Integer>> graph) {

    int n = graph.size();

    boolean[] visited = new boolean[n];
    int components = 0;

    for (int i = 0; i < n; i++) {

        if (!visited[i]) {
            dfs(graph, i, visited);
            components++;
        }
    }

    return components;
}

private void dfs(
        List<List<Integer>> graph,
        int node,
        boolean[] visited) {

    visited[node] = true;

    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited);
        }
    }
}

def count_components(graph):
    n = len(graph)

    visited = [False] * n
    components = 0

    def dfs(node):
        visited[node] = True

        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)

    for i in range(n):

        if not visited[i]:
            dfs(i)
            components += 1

    return components

void dfs(vector<vector<int>>& graph,
         int node,
         vector<bool>& visited) {

    visited[node] = true;

    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited);
        }
    }
}

int countComponents(vector<vector<int>>& graph) {
    int n = graph.size();

    vector<bool> visited(n, false);
    int components = 0;

    for (int i = 0; i < n; i++) {

        if (!visited[i]) {
            dfs(graph, i, visited);
            components++;
        }
    }

    return components;
}

function countComponents(graph) {
  const n = graph.length;

  const visited = new Array(n).fill(false);
  let components = 0;

  function dfs(node) {
    visited[node] = true;

    for (const neighbor of graph[node]) {
      if (!visited[neighbor]) {
        dfs(neighbor);
      }
    }
  }

  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      dfs(i);
      components++;
    }
  }

  return components;
}

What Changed from the Base Template?

Loop through every vertex

Added:

for (int i = 0; i < n; i++)

because one DFS only explores the component containing its starting node.

Count every new DFS

Added:

components++;

because every DFS started from an unvisited node represents one new connected component.

Connected Components = DFS from every unvisited node.

Pattern 3: Path Exists

Code

public boolean hasPath(
        List<List<Integer>> graph,
        int start,
        int target) {

    boolean[] visited = new boolean[graph.size()];

    return dfs(graph, start, target, visited);
}

private boolean dfs(
        List<List<Integer>> graph,
        int node,
        int target,
        boolean[] visited) {

    if (node == target) {
        return true;
    }

    visited[node] = true;

    for (int neighbor : graph.get(node)) {

        if (!visited[neighbor]) {

            if (dfs(graph, neighbor, target, visited)) {
                return true;
            }
        }
    }

    return false;
}

def has_path(graph, start, target):
    visited = [False] * len(graph)

    def dfs(node):
        if node == target:
            return True

        visited[node] = True

        for neighbor in graph[node]:

            if not visited[neighbor]:

                if dfs(neighbor):
                    return True

        return False

    return dfs(start)

bool dfs(vector<vector<int>>& graph,
         int node,
         int target,
         vector<bool>& visited) {

    if (node == target) {
        return true;
    }

    visited[node] = true;

    for (int neighbor : graph[node]) {

        if (!visited[neighbor]) {

            if (dfs(graph, neighbor, target, visited)) {
                return true;
            }
        }
    }

    return false;
}

bool hasPath(vector<vector<int>>& graph,
             int start,
             int target) {
    vector<bool> visited(graph.size(), false);

    return dfs(graph, start, target, visited);
}

function hasPath(graph, start, target) {
  const visited = new Array(graph.length).fill(false);

  function dfs(node) {
    if (node === target) {
      return true;
    }

    visited[node] = true;

    for (const neighbor of graph[node]) {
      if (!visited[neighbor]) {
        if (dfs(neighbor)) {
          return true;
        }
      }
    }

    return false;
  }

  return dfs(start);
}

What Changed from the Base Template?

Added a target

Added:

int target

because we are searching for a specific destination.

Added a base case

if (node == target) {
    return true;
}

Once the target is reached, there is no reason to explore further.

Propagate success upward

if (dfs(graph, neighbor, target, visited)) {
    return true;
}

A successful recursive search causes every previous call to return true.

Path Finding = DFS + Target + Early Return.

Pattern 4: Cycle Detection — Undirected Graph

For an undirected graph, simply seeing an already-visited neighbor does not automatically mean there is a cycle.

Example:

A ----- B
 \     /
   C

When DFS is at B, it can see A again.

That’s normal because the edge is undirected.

Therefore we track the parent.

Code

public boolean hasCycle(List<List<Integer>> graph) {

    int n = graph.size();

    boolean[] visited = new boolean[n];

    for (int i = 0; i < n; i++) {

        if (!visited[i]) {

            if (dfs(graph, i, -1, visited)) {
                return true;
            }
        }
    }

    return false;
}

private boolean dfs(
        List<List<Integer>> graph,
        int node,
        int parent,
        boolean[] visited) {

    visited[node] = true;

    for (int neighbor : graph.get(node)) {

        if (!visited[neighbor]) {

            if (dfs(graph, neighbor, node, visited)) {
                return true;
            }

        } else if (neighbor != parent) {

            return true;
        }
    }

    return false;
}

def has_cycle(graph):
    n = len(graph)

    visited = [False] * n

    def dfs(node, parent):
        visited[node] = True

        for neighbor in graph[node]:

            if not visited[neighbor]:

                if dfs(neighbor, node):
                    return True

            elif neighbor != parent:
                return True

        return False

    for i in range(n):

        if not visited[i]:

            if dfs(i, -1):
                return True

    return False

bool dfs(vector<vector<int>>& graph,
         int node,
         int parent,
         vector<bool>& visited) {

    visited[node] = true;

    for (int neighbor : graph[node]) {

        if (!visited[neighbor]) {

            if (dfs(graph, neighbor, node, visited)) {
                return true;
            }

        } else if (neighbor != parent) {
            return true;
        }
    }

    return false;
}

bool hasCycle(vector<vector<int>>& graph) {
    int n = graph.size();

    vector<bool> visited(n, false);

    for (int i = 0; i < n; i++) {

        if (!visited[i]) {

            if (dfs(graph, i, -1, visited)) {
                return true;
            }
        }
    }

    return false;
}

function hasCycle(graph) {
  const n = graph.length;

  const visited = new Array(n).fill(false);

  function dfs(node, parent) {
    visited[node] = true;

    for (const neighbor of graph[node]) {
      if (!visited[neighbor]) {
        if (dfs(neighbor, node)) {
          return true;
        }
      } else if (neighbor !== parent) {
        return true;
      }
    }

    return false;
  }

  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      if (dfs(i, -1)) {
        return true;
      }
    }
  }

  return false;
}

What Changed from the Base Template?

Added parent tracking

Added:

int parent

because every undirected edge leads back to the node we came from.

Detect a back edge

else if (neighbor != parent) {
    return true;
}

If a neighbor is already visited and is not the parent, we found another connection to an existing part of the DFS tree.

That means a cycle exists.

Undirected Cycle Detection = DFS + Parent Tracking.

Important

Directed graphs use a different technique.

For directed graphs, use:

visited[]
recursionStack[]

or a 3-state array:

0 = unvisited
1 = currently visiting
2 = completely processed

Do not use the undirected parent technique for directed graphs.

Pattern 5: Grid DFS (VERY IMPORTANT)

A grid can be treated as an implicit graph.

Each cell is a node, and neighboring cells are edges.

Typical problems:

Number of Islands
Flood Fill
Surrounded Regions
Connected Regions

Direction Template

private static final int[][] DIRS = {
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1}
};

DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]

const int DIRS[4][2] = {
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1}
};

const DIRS = [
  [1, 0],
  [-1, 0],
  [0, 1],
  [0, -1],
];

These represent:

down
up
right
left

Code

public void dfsGrid(
        int[][] grid,
        int r,
        int c,
        boolean[][] visited) {

    int n = grid.length;
    int m = grid[0].length;

    if (r < 0 || r >= n ||
        c < 0 || c >= m ||
        visited[r][c]) {
        return;
    }

    // Example:
    // if (grid[r][c] is blocked) return;

    visited[r][c] = true;

    for (int[] dir : DIRS) {

        int nr = r + dir[0];
        int nc = c + dir[1];

        dfsGrid(grid, nr, nc, visited);
    }
}

def dfs_grid(grid, r, c, visited):
    n, m = len(grid), len(grid[0])

    if (
        r < 0 or r >= n
        or c < 0 or c >= m
        or visited[r][c]
    ):
        return

    # Example:
    # if grid[r][c] is blocked: return

    visited[r][c] = True

    for dr, dc in DIRS:

        dfs_grid(grid, r + dr, c + dc, visited)

void dfsGrid(vector<vector<int>>& grid,
             int r,
             int c,
             vector<vector<bool>>& visited) {

    int n = grid.size();
    int m = grid[0].size();

    if (r < 0 || r >= n ||
        c < 0 || c >= m ||
        visited[r][c]) {
        return;
    }

    // Example:
    // if (grid[r][c] is blocked) return;

    visited[r][c] = true;

    for (auto& dir : DIRS) {
        dfsGrid(grid, r + dir[0], c + dir[1], visited);
    }
}

function dfsGrid(grid, r, c, visited) {
  const n = grid.length;
  const m = grid[0].length;

  if (
    r < 0 || r >= n ||
    c < 0 || c >= m ||
    visited[r][c]
  ) {
    return;
  }

  // Example:
  // if (grid[r][c] is blocked) return;

  visited[r][c] = true;

  for (const [dr, dc] of DIRS) {
    dfsGrid(grid, r + dr, c + dc, visited);
  }
}

What Changed from the Base Template?

Node becomes a cell

Base:

int node

Changed:

int r, int c

because every grid node has two coordinates.

Generate neighbors using directions

Base:

for (int neighbor : graph.get(node))

Changed:

for (int[] dir : DIRS)

because grid adjacency is generated rather than explicitly stored.

Add boundary checks

if (r < 0 || r >= n ||
    c < 0 || c >= m) {
    return;
}

because recursive calls can move outside the grid.

Important

Usually the problem also has a cell condition.

For example:

if (grid[r][c] == 0) {
    return;
}

Then the DFS only explores valid cells.

Grid DFS = DFS + Coordinates + Directions + Boundary/Validity Checks.

Pattern 6: Backtracking DFS

Backtracking is DFS where we modify state, recurse, then undo the modification.

A classic example is generating permutations.

Code

public List<List<Integer>> permutations(int[] nums) {

    List<List<Integer>> result = new ArrayList<>();
    boolean[] used = new boolean[nums.length];

    backtrack(nums, used, new ArrayList<>(), result);

    return result;
}

private void backtrack(
        int[] nums,
        boolean[] used,
        List<Integer> path,
        List<List<Integer>> result) {

    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }

    for (int i = 0; i < nums.length; i++) {

        if (used[i]) {
            continue;
        }

        used[i] = true;
        path.add(nums[i]);

        backtrack(nums, used, path, result);

        path.remove(path.size() - 1);
        used[i] = false;
    }
}

def permutations(nums):
    result = []
    used = [False] * len(nums)

    def backtrack(path):
        if len(path) == len(nums):
            result.append(path[:])
            return

        for i in range(len(nums)):

            if used[i]:
                continue

            used[i] = True
            path.append(nums[i])

            backtrack(path)

            path.pop()
            used[i] = False

    backtrack([])
    return result

void backtrack(vector<int>& nums,
               vector<bool>& used,
               vector<int>& path,
               vector<vector<int>>& result) {

    if (path.size() == nums.size()) {
        result.push_back(path);
        return;
    }

    for (int i = 0; i < nums.size(); i++) {

        if (used[i]) {
            continue;
        }

        used[i] = true;
        path.push_back(nums[i]);

        backtrack(nums, used, path, result);

        path.pop_back();
        used[i] = false;
    }
}

vector<vector<int>> permutations(vector<int>& nums) {
    vector<vector<int>> result;
    vector<bool> used(nums.size(), false);
    vector<int> path;

    backtrack(nums, used, path, result);

    return result;
}

function permutations(nums) {
  const result = [];
  const used = new Array(nums.length).fill(false);

  function backtrack(path) {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) {
        continue;
      }

      used[i] = true;
      path.push(nums[i]);

      backtrack(path);

      path.pop();
      used[i] = false;
    }
  }

  backtrack([]);
  return result;
}

What Changed from the Base Template?

Added a decision loop

for (int i = 0; i < nums.length; i++)

because every recursive level can choose from multiple candidates.

Track choices

Added:

boolean[] used

because the same element cannot be selected twice in one permutation.

Add the choice

path.add(nums[i]);

Recurse

backtrack(nums, used, path, result);

Undo the choice

path.remove(path.size() - 1);
used[i] = false;

This restores the state so another choice can be explored.

Backtracking = Choose → Recurse → Undo.

DFS Pattern Evolution

Base DFS
    ↓
Traversal
    (+ order list)

Connected Components
    (+ loop over all nodes)

Path Finding
    (+ target + early return)

Undirected Cycle Detection
    (+ parent tracking)

Grid DFS
    (+ coordinates + directions + bounds)

Backtracking DFS
    (+ choices + state + undo)

Common Mistakes

1. Marking visited too late

❌ Wrong:

dfs(graph, neighbor, visited);
visited[neighbor] = true;

This can cause repeated recursive calls.

Mark the node as visited before exploring its neighbors.

visited[node] = true;

2. Forgetting disconnected components

This:

dfs(graph, 0, visited);

only explores the component containing node 0.

For the entire graph:

for (int i = 0; i < n; i++) {
    if (!visited[i]) {
        dfs(graph, i, visited);
    }
}

3. Using DFS for unweighted shortest path

DFS can find a path, but it does not guarantee the shortest path in an unweighted graph.

Use:

BFS for shortest path in an unweighted graph.

4. Using parent tracking for directed cycle detection

Parent tracking is for undirected graphs.

For directed graphs, use:

unvisited
visiting
visited

or a recursion-stack / 3-state approach.

5. Forgetting grid boundaries

Always check:

0 <= row < rows
0 <= col < cols

before accessing:

grid[row][col]

6. Forgetting to undo backtracking state

If you do:

path.add(x);
dfs(...);

you generally need:

path.remove(path.size() - 1);

after recursion if the path is shared across branches.

Rule

Every mutation made for one branch must be restored before trying the next branch.

7. Stack overflow on deep graphs

Recursive DFS can overflow the Java call stack on very deep graphs.

For iterative DFS, prefer:

Deque<Integer> stack = new ArrayDeque<>();

stack.push(start);

while (!stack.isEmpty()) {
    int node = stack.pop();

    // process node
}

Avoid relying on the legacy Stack<Integer> class for new Java code.

Complexity

For a graph with V vertices and E edges:

Time

O(V + E)

Each vertex and edge is processed a constant number of times.

Space

O(V)

for:

visited[]
recursion stack
auxiliary structures

For a grid with R × C cells:

Time:  O(R × C)
Space: O(R × C)

The space can come from the visited array and recursion stack.

Recognition Cheat Sheet

If you see…	Think…
Explore a graph deeply	DFS
Visit all reachable nodes	DFS
Connected components	DFS + outer loop
Does a path exist?	DFS
Undirected cycle	DFS + parent
Directed cycle	DFS + recursion state
Islands / regions	Grid DFS
Flood fill	Grid DFS
Generate permutations	Backtracking DFS
Generate combinations	Backtracking DFS
Generate subsets	Backtracking DFS
Shortest path in unweighted graph	BFS

DFS vs BFS

Problem	Better Choice
Explore deeply	DFS
Connected components	DFS / BFS
Cycle detection	DFS
Generate all possibilities	DFS / Backtracking
Shortest path, unweighted	BFS
Minimum number of steps	BFS
Level-by-level processing	BFS
Grid shortest path	BFS
Grid regions / islands	DFS or BFS

Earn Premium with Referrals

Pattern Table

Mental Trigger

1. Generic DFS Template (Base)

Depth-First Search

Pattern 1: Basic DFS Traversal

Code

What Changed from the Base Template?

Added traversal storage

Record each visited node

Pattern 2: Connected Components

Code

What Changed from the Base Template?

Loop through every vertex

Count every new DFS

Pattern 3: Path Exists

Code

What Changed from the Base Template?

Added a target

Added a base case

Propagate success upward

Pattern 4: Cycle Detection — Undirected Graph

Code

What Changed from the Base Template?

Added parent tracking

Detect a back edge

Important

Pattern 5: Grid DFS (VERY IMPORTANT)

Direction Template

Code

What Changed from the Base Template?

Node becomes a cell

Generate neighbors using directions

Add boundary checks

Important

Pattern 6: Backtracking DFS

Code

What Changed from the Base Template?

Added a decision loop

Track choices

Add the choice

Recurse

Undo the choice

DFS Pattern Evolution

Common Mistakes

1. Marking visited too late

2. Forgetting disconnected components

3. Using DFS for unweighted shortest path

4. Using parent tracking for directed cycle detection

5. Forgetting grid boundaries

6. Forgetting to undo backtracking state

Rule

7. Stack overflow on deep graphs

Complexity

Time

Space

Recognition Cheat Sheet

DFS vs BFS

Premium Content

My Private Notes