DFS Depth First Search on Graph in DSA Java

Mental Model

DFS explores as far as possible along each branch before backtracking. It dives deep into one path before trying another.

Analogy: Imagine exploring a maze by always taking the first unexplored path you see until you hit a dead end, then backtracking to try other paths.

Graph adjacency list:
0 -> [1, 2]
1 -> [2]
2 -> [0, 3]
3 -> [3]

Start at node 2 ↑

Dry Run Walkthrough

Input: Graph with edges: 0->1, 0->2, 1->2, 2->0, 2->3, 3->3; start DFS at node 2

Goal: Visit all nodes reachable from node 2 using DFS order

Step 1: Start DFS at node 2, mark 2 visited

Visited: {2}
Stack: [2]
Order: 2

Why: We begin exploring from node 2

Step 2: Explore neighbor 0 of node 2, mark 0 visited

Visited: {2, 0}
Stack: [2, 0]
Order: 2 -> 0

Why: Go deeper to node 0 before other neighbors

Step 3: Explore neighbor 1 of node 0, mark 1 visited

Visited: {2, 0, 1}
Stack: [2, 0, 1]
Order: 2 -> 0 -> 1

Why: Continue deep exploration from node 0 to 1

Step 4: Explore neighbor 2 of node 1, already visited, backtrack

Visited: {2, 0, 1}
Stack: [2, 0]
Order: 2 -> 0 -> 1

Why: Node 2 visited, no new nodes here, backtrack to 0

Step 5: Explore neighbor 2 of node 0, already visited, backtrack

Visited: {2, 0, 1}
Stack: [2]
Order: 2 -> 0 -> 1

Why: All neighbors of 0 visited, backtrack to 2

Step 6: Explore neighbor 3 of node 2, mark 3 visited

Visited: {2, 0, 1, 3}
Stack: [2, 3]
Order: 2 -> 0 -> 1 -> 3

Why: Explore remaining neighbor 3 from node 2

Step 7: Explore neighbor 3 of node 3, already visited, backtrack

Visited: {2, 0, 1, 3}
Stack: [2]
Order: 2 -> 0 -> 1 -> 3

Why: Self-loop on 3 already visited, backtrack

Step 8: All neighbors of 2 visited, DFS complete

Visited: {2, 0, 1, 3}
Stack: []
Order: 2 -> 0 -> 1 -> 3

Why: No more nodes to explore

Result:

Visited order: 2 -> 0 -> 1 -> 3

Annotated Code

DSA Java

import java.util.*;

public class DFSGraph {
    private final int vertices;
    private final List<List<Integer>> adjList;

    public DFSGraph(int v) {
        vertices = v;
        adjList = new ArrayList<>();
        for (int i = 0; i < v; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int src, int dest) {
        adjList.get(src).add(dest);
    }

    public void dfs(int start) {
        boolean[] visited = new boolean[vertices];
        List<Integer> order = new ArrayList<>();
        dfsUtil(start, visited, order);
        for (int i = 0; i < order.size(); i++) {
            System.out.print(order.get(i));
            if (i != order.size() - 1) {
                System.out.print(" -> ");
            }
        }
        System.out.println();
    }

    private void dfsUtil(int node, boolean[] visited, List<Integer> order) {
        visited[node] = true; // mark current node visited
        order.add(node); // record visit order
        for (int neighbor : adjList.get(node)) {
            if (!visited[neighbor]) {
                dfsUtil(neighbor, visited, order); // explore deeper
            }
        }
    }

    public static void main(String[] args) {
        DFSGraph graph = new DFSGraph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        graph.dfs(2); // start DFS at node 2
    }
}

visited[node] = true; // mark current node visited

mark current node as visited to avoid revisiting

order.add(node); // record visit order

record the order of node visits

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

iterate over neighbors to explore deeper

if (!visited[neighbor]) {

only visit neighbors not visited yet

dfsUtil(neighbor, visited, order); // explore deeper

recursive call to dive deeper into graph

Output

2 -> 0 -> 1 -> 3

Complexity Analysis

Time: O(V + E) because DFS visits every vertex and edge once

Space: O(V) for the visited array and recursion stack in worst case

vs Alternative: Compared to BFS which uses a queue and explores level by level, DFS uses recursion and explores depth first; both have similar time but different traversal order

Edge Cases

Empty graph (no vertices)

DFS does nothing, no nodes to visit

DSA Java

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

Graph with single node and no edges

DFS visits the single node and stops

DSA Java

visited[node] = true; // mark current node visited

Graph with cycles (like node 3 pointing to itself)

DFS avoids infinite loops by checking visited nodes

DSA Java

if (!visited[neighbor]) { dfsUtil(neighbor, visited, order); }

When to Use This Pattern

When you need to explore all nodes reachable from a start node deeply before backtracking, use DFS because it naturally follows paths to their end before trying alternatives.

Common Mistakes

Mistake: Not marking nodes as visited before recursive calls, causing infinite loops
Fix: Mark the node as visited immediately when entering dfsUtil to prevent revisiting

Mistake: Visiting neighbors without checking if they are already visited
Fix: Add a visited check before recursive calls to avoid cycles

Summary

DFS visits nodes by going deep along each path before backtracking.

Use DFS when you want to explore all paths from a start node deeply or check connectivity.

The key is to mark nodes visited to avoid revisiting and infinite loops.

Practice

1. What is the main idea behind Depth First Search (DFS) on a graph?

easy

A. Randomly visit nodes until all are visited

B. Visit all neighbors of a node before moving deeper

C. Visit nodes in order of their distance from the start node

D. Explore as far as possible along each branch before backtracking

Solution

1. Step 1: Understand DFS traversal

   DFS explores a graph by going deep into one branch before backtracking to explore other branches.

2. Step 2: Compare options with DFS behavior

   Explore as far as possible along each branch before backtracking matches this behavior exactly, while others describe BFS or incorrect methods.

3. Final Answer:

   Explore as far as possible along each branch before backtracking -> Option D

4. Quick Check:

   DFS = deep exploration first [OK]

Hint: DFS goes deep first, BFS goes wide first [OK]

Common Mistakes:

• Confusing DFS with BFS
• Thinking DFS visits neighbors first
• Assuming DFS visits nodes by distance

2. Which of the following is the correct way to start a DFS traversal from node 0 in Java using recursion?

easy

A. dfs(0, visited, graph);

B. DFS(visited, graph, 0);

C. dfs(graph, 0, visited);

D. dfs(visited, 0, graph);

Solution

1. Step 1: Identify typical DFS method signature

   Common DFS signature is dfs(currentNode, visitedArray, graph).

2. Step 2: Match options to this signature

   dfs(0, visited, graph); matches the order: node, visited, graph. Others have wrong parameter order.

3. Final Answer:

   dfs(0, visited, graph); -> Option A

4. Quick Check:

   Correct parameter order = dfs(node, visited, graph) [OK]

Hint: DFS method usually starts with node, visited, graph [OK]

Common Mistakes:

• Mixing parameter order
• Using uppercase method name 'DFS'
• Passing graph before node

3. Given the graph adjacency list: graph = {{1, 2}, {0, 3}, {0}, {1}} and starting DFS from node 0, what is the order of nodes visited?

medium

A. [0, 1, 3, 2]

B. [0, 2, 1, 3]

C. [0, 1, 2, 3]

D. [0, 3, 1, 2]

Solution

1. Step 1: Start DFS at node 0 and visit neighbors

   From 0, neighbors are 1 and 2. DFS visits 1 first (assuming adjacency order).

2. Step 2: From node 1, visit its neighbors

   Neighbors of 1 are 0 (visited) and 3. Visit 3 next.

3. Step 3: Backtrack and visit remaining neighbors

   After 3, backtrack to 0 and visit 2.

4. Final Answer:

   [0, 1, 3, 2] -> Option A

5. Quick Check:

   DFS order = 0,1,3,2 [OK]

Hint: Follow neighbors deeply in adjacency order [OK]

Common Mistakes:

• Visiting neighbors in wrong order
• Not backtracking correctly
• Confusing BFS order with DFS

4. What is wrong with this DFS code snippet in Java?

void dfs(int node, boolean[] visited, List<Integer>[] graph) {
  visited[node] = true;
  for (int neighbor : graph[node]) {
    if (visited[neighbor]) {
      dfs(neighbor, visited, graph);
    }
  }
}

medium

A. It does not mark nodes as visited

B. It calls dfs on already visited neighbors causing infinite recursion

C. It uses wrong data types for graph

D. It misses the base case for recursion

Solution

1. Step 1: Check visited condition before recursive call

   The code calls dfs(neighbor) only if visited[neighbor] is true, which means already visited.

2. Step 2: Identify the problem caused

   This causes infinite recursion because it revisits nodes already visited instead of skipping them.

3. Final Answer:

   It calls dfs on already visited neighbors causing infinite recursion -> Option B

4. Quick Check:

   Call dfs only if neighbor not visited [OK]

Hint: Call dfs only if neighbor is NOT visited [OK]

Common Mistakes:

• Calling dfs on visited nodes
• Forgetting to mark visited nodes
• Incorrect loop over neighbors

5. You want to find if there is a path between node 0 and node 4 in this graph:

graph = {{1, 2}, {0, 3}, {0, 4}, {1}, {2}}

Which DFS approach correctly determines if node 4 is reachable from node 0?

hard

A. Run DFS from 4, stop and return true if node 0 is found during traversal

B. Run DFS from 0 and count all visited nodes without checking for 4

C. Run DFS from 0, stop and return true if node 4 is found during traversal

D. Run DFS from 0 but skip node 2 to avoid cycles

Solution

1. Step 1: Understand the goal

   We want to check if node 4 is reachable from node 0, so start DFS at 0.

2. Step 2: Use DFS to find target node

   During DFS, if node 4 is found, stop and return true immediately.

3. Step 3: Evaluate options

   Run DFS from 0, stop and return true if node 4 is found during traversal matches this approach. Run DFS from 4, stop and return true if node 0 is found during traversal starts from wrong node. Run DFS from 0 and count all visited nodes without checking for 4 ignores target. Run DFS from 0 but skip node 2 to avoid cycles skips nodes incorrectly.

4. Final Answer:

   Run DFS from 0, stop and return true if node 4 is found during traversal -> Option C

5. Quick Check:

   DFS from start, stop on target found [OK]

Hint: Stop DFS early when target node is found [OK]

Common Mistakes:

• Starting DFS from wrong node
• Not checking for target during traversal
• Skipping nodes that are part of path