DFS Depth First Search on Graph in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start DFS from the given node.

DSA Java

void dfs(int node) {
    visited[node] = true;
    System.out.print(node + " -> ");
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs([1]);
        }
    }
}

Drag options to blanks, or click blank then click option'

Anode

Bneighbor

Cvisited

Dgraph

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'node' instead of 'neighbor' causes infinite recursion.

Using 'visited' or 'graph' as argument causes errors.

We call dfs recursively on each unvisited neighbor to explore deeper.

2fill in blank

medium

Complete the code to initialize the visited array for DFS.

DSA Java

boolean[] visited = new boolean[[1]];

Drag options to blanks, or click blank then click option'

Avisited.length

Bgraph[0].length

Cgraph.length

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using graph[0].length assumes a matrix, but graph is adjacency list.

Using visited.length before initialization causes errors.

The visited array size should match the number of nodes, which is graph.length.

3fill in blank

hard

Fix the error in the DFS method to avoid revisiting nodes.

DSA Java

void dfs(int node) {
    if (visited[node]) return;
    visited[node] = true;
    System.out.print(node + " -> ");
    for (int neighbor : graph[node]) {
        dfs([1]);
    }
}

Drag options to blanks, or click blank then click option'

Aneighbor

Bnode

Cvisited[node]

Dgraph[node]

Attempts:

3 left

💡 Hint

Common Mistakes

Calling dfs(node) inside the loop causes stack overflow.

Using visited[node] or graph[node] as argument causes errors.

We must call dfs on each neighbor, not the current node, to explore all connected nodes.

4fill in blank

hard

Fill both blanks to create a DFS method that prints nodes in order.

DSA Java

void dfs(int [1]) {
    visited[[2]] = true;
    System.out.print([2] + " -> ");
    for (int neighbor : graph[[2]]) {
        if (!visited[neighbor]) {
            dfs(neighbor);
        }
    }
}

Drag options to blanks, or click blank then click option'

Anode

Bneighbor

Cvisited

Dgraph

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variables for parameter and visited index causes errors.

Using 'neighbor' instead of 'node' in visited causes wrong marking.

The parameter and visited index must be the same node variable to mark and print correctly.

5fill in blank

hard

Fill all three blanks to create a DFS that counts visited nodes.

DSA Java

int count = 0;
void dfs(int [1]) {
    visited[[2]] = true;
    count[3];
    for (int neighbor : graph[[2]]) {
        if (!visited[neighbor]) {
            dfs(neighbor);
        }
    }
}

Drag options to blanks, or click blank then click option'

Anode

B++

Cnode++

Dneighbor

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'node++' instead of 'count++' does not increment count.

Using 'neighbor' in visited index causes errors.

Use 'node' as parameter and visited index, and increment count with ++ to track visited nodes.

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