DFS Depth First Search on Graph in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of DFS traversal on a simple graph

What is the output of the following DFS traversal starting from node 0?

DSA Java

import java.util.*;

class Graph {
    private final Map<Integer, List<Integer>> adjList = new HashMap<>();

    void addEdge(int u, int v) {
        adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
        adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
    }

    void dfs(int start, Set<Integer> visited, List<Integer> result) {
        visited.add(start);
        result.add(start);
        for (int neighbor : adjList.getOrDefault(start, Collections.emptyList())) {
            if (!visited.contains(neighbor)) {
                dfs(neighbor, visited, result);
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph g = new Graph();
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 4);

        List<Integer> result = new ArrayList<>();
        g.dfs(0, new HashSet<>(), result);
        System.out.println(result);
    }
}

A [0, 3, 1, 2, 4]

B [0, 1, 3, 2, 4]

C [0, 1, 2, 3, 4]

D [0, 2, 4, 1, 3]

💡 Hint

Remember DFS explores as far as possible along each branch before backtracking.

Starting from 0, DFS visits 1 first (from adjacency list order), then 3 from 1, backtracks to 0, then visits 2, and finally 4 from 2.

🧠 Conceptual

intermediate

DFS stack vs recursion behavior

Which statement best describes how DFS uses the call stack or an explicit stack during traversal?

A DFS uses a priority queue to always visit the smallest numbered node next.

B DFS uses a hash map to store nodes in the order they are visited to avoid revisiting.

C DFS uses a queue to keep track of nodes to visit next, ensuring breadth-first order.

D DFS uses a stack (either call stack via recursion or explicit stack) to explore nodes deeply before backtracking.

💡 Hint

Think about how DFS goes deep before exploring siblings.

DFS explores as far as possible along each branch before backtracking, which is naturally implemented using a stack structure.

🔧 Debug

advanced

Identify the error in DFS implementation

What error will this DFS code produce when run on a graph with cycles?

DSA Java

void dfs(int node) {
    System.out.print(node + " ");
    for (int neighbor : adjList.get(node)) {
        dfs(neighbor);
    }
}

A StackOverflowError due to infinite recursion on cycles

B NullPointerException because adjList is empty

C No error, prints nodes in DFS order correctly

D ConcurrentModificationException due to modifying list during iteration

💡 Hint

Think about what happens if a node is visited multiple times without tracking.

Without marking visited nodes, DFS will recurse infinitely on cycles causing a stack overflow.

🚀 Application

advanced

DFS to find connected components count

Given an undirected graph, which code snippet correctly counts the number of connected components using DFS?

DSA Java

int countComponents(int n, int[][] edges) {
    Map<Integer, List<Integer>> graph = new HashMap<>();
    for (int i = 0; i < n; i++) graph.put(i, new ArrayList<>());
    for (int[] e : edges) {
        graph.get(e[0]).add(e[1]);
        graph.get(e[1]).add(e[0]);
    }
    boolean[] visited = new boolean[n];
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, graph, visited);
            count++;
        }
    }
    return count;
}

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

A Returns the number of connected components correctly

B Returns the number of edges instead of components

C Returns zero always because visited array is not updated

D Throws NullPointerException due to missing graph initialization

💡 Hint

Each DFS call from an unvisited node marks one component.

The code initializes the graph, uses DFS to mark visited nodes, and counts how many times DFS starts, which equals connected components.

❓ Predict Output

expert

Output of DFS on directed graph with back edges

What is the output of the DFS traversal starting from node 1 on this directed graph?

DSA Java

import java.util.*;

class DirectedGraph {
    private final Map<Integer, List<Integer>> adjList = new HashMap<>();

    void addEdge(int u, int v) {
        adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
    }

    void dfs(int node, Set<Integer> visited, List<Integer> result) {
        visited.add(node);
        result.add(node);
        for (int neighbor : adjList.getOrDefault(node, Collections.emptyList())) {
            if (!visited.contains(neighbor)) {
                dfs(neighbor, visited, result);
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        DirectedGraph g = new DirectedGraph();
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        g.addEdge(3, 1); // back edge creating a cycle
        g.addEdge(2, 4);

        List<Integer> result = new ArrayList<>();
        g.dfs(1, new HashSet<>(), result);
        System.out.println(result);
    }
}

A [1, 3, 2, 4]

B [1, 2, 4, 3]

C [1, 2, 3, 4]

D [1, 4, 2, 3]

💡 Hint

DFS avoids revisiting nodes already visited, even in cycles.

Starting at 1, DFS visits 2, then 3, then back edge to 1 is ignored, then visits 4 from 2. So order is [1, 2, 3, 4].

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