Depth First Search (DFS)

Imagine you're exploring a maze.

You enter through one path and keep walking as deep as possible. When you reach a dead end, you go back to the previous junction and try another path.

That's the basic idea behind Depth First Search, or DFS.

Depth First Search is a graph traversal algorithm that explores as far as possible along one path before backtracking and exploring another path.

DFS is one of the two fundamental graph traversal techniques:

DFS → Depth First Search
BFS → Breadth First Search

While BFS explores level by level, DFS explores depth first.

How DFS Works

Consider this graph:

        0
       / \
      1   2
     / \
    3   4

Starting from 0, one possible DFS traversal is:

0 → 1 → 3 → 4 → 2

The exact order can vary depending on the order of neighbors in the adjacency list.

The important idea is:

0
↓
1
↓
3

DFS goes deep into one branch.

When it reaches a node with no unvisited neighbor, it backtracks:

3
↑
1

Then it explores another branch:

1
↓
4

Finally, it goes back and explores 2.

Why Is It Called Depth First?

Look at:

        0
       / \
      1   2
     / \
    3   4

BFS would explore:

0 → 1 → 2 → 3 → 4

because it visits level by level.

DFS instead explores:

0 → 1 → 3

before coming back:

3 → 1 → 4

So the basic difference is:

DFS → Go deep first
BFS → Go wide first

DFS Uses a Stack

The most important thing to remember is:

DFS uses a Stack.

A stack follows:

LIFO
Last In, First Out

For example:

10
20
30 ← Top

30 is removed first.

DFS needs this behavior because when it discovers a new path, it wants to continue down that path before returning to earlier choices.

DFS can be implemented in two main ways:

DFS
├── Recursion
└── Explicit Stack

DFS Using Recursion

DFS is naturally implemented using recursion.

Consider:

        0
       / \
      1   2
     / \
    3   4

The recursive function does this:

Visit 0
 ↓
Visit 1
 ↓
Visit 3
 ↓
Backtrack
 ↓
Visit 4
 ↓
Backtrack
 ↓
Visit 2

The recursion call stack acts like a stack.

DFS Algorithm

The basic DFS algorithm is:

DFS(node):

    mark node as visited

    process node

    for every neighbor:

        if neighbor is not visited:

            DFS(neighbor)

In pseudocode:

DFS(start):

    mark start as visited

    for each neighbor of start:

        if neighbor is not visited:

            DFS(neighbor)

Why Do We Need visited[]?

This is extremely important.

Graphs can contain cycles.

For example:

A ─ B
|   |
C ─ D

There is a cycle:

A → B → D → C → A

If DFS doesn't keep track of visited vertices, it could continue forever:

A → B → D → C → A → B → D → ...

So we use:

boolean[] visited =
    new boolean[vertices];

When we visit a node:

visited[node] = true;

Then we never visit that node again during that traversal.

DFS in Java

Let's write a simple DFS:

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

    visited[node] = true;

    System.out.print(node + " ");

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

        if (!visited[neighbor]) {

            dfs(
                neighbor,
                graph,
                visited
            );
        }
    }
}

The most important lines are:

visited[node] = true;

and:

dfs(neighbor, graph, visited);

The second line is what allows DFS to go deeper.

Complete DFS Example

Consider:

        0
       / \
      1   2
     / \
    3   4

We can build it using an adjacency list:

import java.util.ArrayList;

class Main {

    static void addEdge(
        ArrayList<ArrayList<Integer>> graph,
        int u,
        int v
    ) {

        graph.get(u).add(v);
        graph.get(v).add(u);
    }

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

        visited[node] = true;

        System.out.print(node + " ");

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

            if (!visited[neighbor]) {

                dfs(
                    neighbor,
                    graph,
                    visited
                );
            }
        }
    }

    public static void main(String[] args) {

        int vertices = 5;

        ArrayList<ArrayList<Integer>> graph =
            new ArrayList<>();

        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }

        addEdge(graph, 0, 1);
        addEdge(graph, 0, 2);
        addEdge(graph, 1, 3);
        addEdge(graph, 1, 4);

        boolean[] visited =
            new boolean[vertices];

        dfs(0, graph, visited);
    }
}

One possible output is:

0 1 3 4 2

Again, DFS order depends on the order of neighbors in the adjacency list.

DFS Step by Step

Let's understand exactly what happens.

Graph:

        0
       / \
      1   2
     / \
    3   4

Start:

DFS(0)

Mark:

visited[0] = true

Then look at neighbors.

First neighbor is 1.

So:

DFS(1)

Mark:

visited[1] = true

Its first unvisited neighbor is 3.

So:

DFS(3)

3 has no unvisited neighbors.

Return to 1.

Now explore 4:

DFS(4)

4 has no unvisited neighbors.

Return to 0.

Now explore 2:

DFS(2)

Traversal:

0 → 1 → 3 → 4 → 2

This is the depth-first behavior.

The Call Stack

The recursive calls can be visualized as a stack.

When we have:

DFS(0)

the stack is:

DFS(0)

Then:

DFS(1)

DFS(1)
DFS(0)

Then:

DFS(3)

DFS(3)
DFS(1)
DFS(0)

When 3 finishes, it is removed from the stack:

DFS(1)
DFS(0)

Then DFS continues with another neighbor.

This is why recursion works naturally for DFS.

Iterative DFS Using a Stack

We can also implement DFS without recursion.

Instead, we explicitly create a stack.

import java.util.Stack;

static void dfs(
    int start,
    ArrayList<ArrayList<Integer>> graph
) {

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

    Stack<Integer> stack =
        new Stack<>();

    stack.push(start);

    while (!stack.isEmpty()) {

        int node = stack.pop();

        if (visited[node]) {
            continue;
        }

        visited[node] = true;

        System.out.print(node + " ");

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

            if (!visited[neighbor]) {
                stack.push(neighbor);
            }
        }
    }
}

The fundamental idea is still:

Stack
 ↓
Take top
 ↓
Visit node
 ↓
Add neighbors
 ↓
Continue deeper

The exact traversal order can differ from recursive DFS depending on the order in which neighbors are pushed onto the stack.

DFS vs BFS

This is one of the most important DSA comparisons.

Consider:

        0
       / \
      1   2
     / \
    3   4

One possible DFS:

0 → 1 → 3 → 4 → 2

BFS:

0 → 1 → 2 → 3 → 4

The difference:

A simple memory trick:

DFS → Stack
BFS → Queue

DFS for Connected Components

Suppose we have:

0 ─ 1       3 ─ 4
|             \
2              5

There are two connected components:

Component 1:
0, 1, 2

Component 2:
3, 4, 5

We can find them using DFS.

The idea is:

for every vertex:

    if it is not visited:

        DFS(vertex)

        componentCount++

Java:

static int countComponents(
    ArrayList<ArrayList<Integer>> graph
) {

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

    int count = 0;

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

        if (!visited[i]) {

            count++;

            dfs(i, graph, visited);
        }
    }

    return count;
}

Each DFS explores one complete connected component.

DFS for Cycle Detection

DFS is commonly used to detect cycles.

Consider:

A ─ B
|   |
C ─ D

We can travel:

A → B → D → C → A

which means a cycle exists.

For an undirected graph, DFS can keep track of the parent node.

The idea is:

Current node
     ↓
Visit neighbor
     ↓
If neighbor is already visited
and isn't the parent
     ↓
Cycle exists

For directed graphs, cycle detection is handled differently because the meaning of an already visited vertex depends on whether it's still in the current DFS path.

DFS for Topological Sorting

DFS is also useful for Topological Sorting.

Consider course dependencies:

Java
 ↓
DSA
 ↓
Algorithms
 ↓
Advanced Algorithms

This can be represented as a directed graph:

Java → DSA
DSA → Algorithms
Algorithms → Advanced Algorithms

DFS can be used to produce a valid ordering.

A common technique is:

Visit node
 ↓
Visit all dependencies
 ↓
Add node to stack

Finally, popping/reversing the resulting order gives a topological ordering.

Topological sorting is useful for:

• Course prerequisites

• Build systems

• Task dependencies

• Package dependencies

DFS for Path Finding

DFS can also determine whether a path exists between two vertices.

Suppose:

A ─ B ─ C
    |
    D

We want to know:

Can A reach D?

Start DFS from A:

A
 ↓
B
 ↓
D

We found it.

The basic idea is:

DFS(start)

If current == target:
    found

Otherwise:
    explore unvisited neighbors

DFS and Backtracking

DFS is closely related to backtracking.

Consider a maze:

S . # .
. . # .
# . . E

You can explore one possible path:

S
 ↓
 .
 ↓
 .
 ↓
 .

If you reach a dead end:

Dead end
   ↓
Backtrack
   ↓
Try another path

This is the same basic pattern as DFS.

That's why DFS appears in:

• Maze solving

• Sudoku

• N-Queens

• Permutations

• Combinations

• Path finding

DFS on a Grid

A grid can be treated as a graph.

For example:

1 1 0
0 1 0
1 0 1

Each cell can represent a vertex.

Adjacent cells are connected.

DFS can be used to explore:

• Islands

• Connected regions

• Mazes

• Flood fill

• Image components

For example, the famous Number of Islands problem can be solved using DFS.

When we find an unvisited land cell:

1

we start DFS and mark the entire connected island as visited.

Number of Islands

Consider:

1 1 0 0
1 0 0 1
0 0 1 1
1 0 0 0

Each 1 represents land.

DFS can explore every connected group of land.

Conceptually:

Find unvisited 1
       ↓
Start DFS
       ↓
Mark entire island visited
       ↓
Count +1
       ↓
Continue

This is one of the most common applications of DFS on a grid.

DFS on a Directed Graph

DFS works with directed graphs as well.

Consider:

A → B → C
    ↓
    D

Starting from A:

A → B → C
      ↓
      D

The traversal follows the direction of the edges.

If we have:

A → B

DFS can move:

A → B

but cannot automatically move:

B → A

unless a reverse edge exists.

DFS and Recursion Depth

Recursive DFS is elegant, but there is one practical concern.

Consider a graph shaped like a long chain:

0 → 1 → 2 → 3 → 4 → 5 → ... → n

DFS recursion may create a very deep call stack.

For a sufficiently large graph, this can cause a stack overflow.

In such cases, an iterative DFS using an explicit stack may be preferable.

So:

Small/moderate depth
→ Recursive DFS is convenient

Very deep traversal
→ Iterative DFS can avoid call-stack limitations

DFS Complexity

For an adjacency-list representation:

Time Complexity → O(V + E)

Why?

DFS can visit every vertex:

V

and inspect every edge:

E

Therefore:

O(V + E)

The auxiliary space is:

O(V)

for the visited structure and the recursion/explicit stack in the worst case, excluding the graph's own storage.

So remember:

DFS

Time  → O(V + E)
Space → O(V)

DFS with an Adjacency Matrix

If the graph is represented using an adjacency matrix, DFS may need to scan all possible neighbors for every vertex.

Therefore:

Time → O(V²)

So:

Adjacency List + DFS
        ↓
O(V + E)

while:

Adjacency Matrix + DFS
        ↓
O(V²)

Common DFS Problems

Once you understand basic DFS, you'll encounter many variations.

1. Connected Components

Find separate groups of connected vertices.

2. Cycle Detection

Determine whether a graph contains a cycle.

3. Path Finding

Determine whether a path exists between two vertices.

4. Number of Islands

Explore connected regions in a grid.

5. Flood Fill

Explore neighboring cells.

6. Topological Sorting

Order vertices based on dependencies.

7. Backtracking

Explore possible solutions and undo choices.

8. Bipartite Graph

DFS can also be used to color and test whether a graph is bipartite.

A Complete Java Example

Here's a complete DFS implementation using an adjacency list:

import java.util.ArrayList;

class Main {

    static void addEdge(
        ArrayList<ArrayList<Integer>> graph,
        int u,
        int v
    ) {

        graph.get(u).add(v);
        graph.get(v).add(u);
    }

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

        visited[node] = true;

        System.out.print(node + " ");

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

            if (!visited[neighbor]) {

                dfs(
                    neighbor,
                    graph,
                    visited
                );
            }
        }
    }

    public static void main(String[] args) {

        int vertices = 6;

        ArrayList<ArrayList<Integer>> graph =
            new ArrayList<>();

        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }

        addEdge(graph, 0, 1);
        addEdge(graph, 0, 2);
        addEdge(graph, 1, 3);
        addEdge(graph, 1, 4);
        addEdge(graph, 2, 5);

        boolean[] visited =
            new boolean[vertices];

        dfs(0, graph, visited);
    }
}

One possible output:

0 1 3 4 2 5

The exact order depends on the adjacency-list ordering.

BFS vs DFS: When Should You Use Which?

This is a common interview question.

Use BFS when:

You need:

Shortest path in an unweighted graph
Minimum number of moves
Level-by-level traversal
Nodes at distance K
Multi-source expansion

Think:

BFS → Queue → Levels

Use DFS when:

You need:

Deep exploration
Connected components
Cycle detection
Topological sorting
Backtracking
Path exploration
Grid exploration

Think:

DFS → Stack → Depth

The Main Idea

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

The basic process is:

Start
 ↓
Mark visited
 ↓
Explore a neighbor
 ↓
Go deeper
 ↓
Continue
 ↓
Backtrack when necessary

The key relationship is:

DFS
 ↓
Stack
 ↓
LIFO

DFS can be implemented using:

Recursion

or:

Explicit Stack

Its standard complexity with an adjacency list is:

Time  → O(V + E)
Space → O(V)

The most important applications include:

DFS
├── Connected Components
├── Cycle Detection
├── Path Finding
├── Topological Sorting
├── Number of Islands
├── Flood Fill
└── Backtracking

When a problem asks you to explore a graph deeply, discover connected regions, detect cycles, or explore all possible paths, DFS should be one of the first techniques you consider.

The simplest memory trick is:

BFS → Queue → Breadth → Levels
DFS → Stack → Depth → Backtracking