DFS Depth First Search on Graph in DSA Java - Build from Scratch

DFS Depth First Search on Graph

📖 Scenario: You are working with a simple map of cities connected by roads. You want to explore all cities reachable from a starting city using Depth First Search (DFS).

🎯 Goal: Build a Java program that uses DFS to visit all cities connected to a given starting city in a graph represented by an adjacency list.

📋 What You'll Learn

Create a graph using a HashMap where keys are city names (Strings) and values are lists of connected cities (ArrayList)

Create a HashSet to keep track of visited cities

Implement a DFS method that visits cities recursively

Print the order of cities visited starting from a given city

💡 Why This Matters

🌍 Real World

DFS is used in maps, social networks, and puzzles to explore connected places or items.

💼 Career

Understanding DFS helps in software development roles involving graph algorithms, pathfinding, and network analysis.

1

Create the graph data structure

Create a HashMap called graph with these exact entries: "A" connected to ["B", "C"], "B" connected to ["D"], "C" connected to ["E"], "D" connected to [], and "E" connected to [].

DSA Java

import java.util.*;

public class DFSGraph {
    public static void main(String[] args) {
        // Your code here
    }
}

Hint

Use HashMap and ArrayList to create the graph. Use Arrays.asList to create lists of connected cities.

2

Create the visited set

Create a HashSet called visited to keep track of visited cities.

DSA Java

import java.util.*;

public class DFSGraph {
    public static void main(String[] args) {
        HashMap> graph = new HashMap();
        graph.put("A", new ArrayList(Arrays.asList("B", "C")));
        graph.put("B", new ArrayList(Arrays.asList("D")));
        graph.put("C", new ArrayList(Arrays.asList("E")));
        graph.put("D", new ArrayList());
        graph.put("E", new ArrayList());

        // Create a HashSet called visited
        // Your code here
    }
}

Hint

Use HashSet<String> visited = new HashSet<>(); to create the visited set.

3

Implement the DFS method

Add a static method called dfs that takes parameters graph (HashMap<String, ArrayList<String>>), city (String), and visited (HashSet<String>). The method should: check if city is already in visited, if yes return; otherwise add city to visited, then recursively call dfs on all connected cities from graph.get(city).

DSA Java

import java.util.*;

public class DFSGraph {
    public static void main(String[] args) {
        HashMap> graph = new HashMap();
        graph.put("A", new ArrayList(Arrays.asList("B", "C")));
        graph.put("B", new ArrayList(Arrays.asList("D")));
        graph.put("C", new ArrayList(Arrays.asList("E")));
        graph.put("D", new ArrayList());
        graph.put("E", new ArrayList());

        HashSet visited = new HashSet();

        // Your code here
    }
}

Hint

Use recursion to visit each city. Check if city is visited, add it if not, then call dfs on neighbors.

4

Run DFS and print visited cities

In the main method, call dfs(graph, "A", visited) to start DFS from city "A". Then print the visited set.

DSA Java

import java.util.*;

public class DFSGraph {
    public static void main(String[] args) {
        HashMap> graph = new HashMap();
        graph.put("A", new ArrayList(Arrays.asList("B", "C")));
        graph.put("B", new ArrayList(Arrays.asList("D")));
        graph.put("C", new ArrayList(Arrays.asList("E")));
        graph.put("D", new ArrayList());
        graph.put("E", new ArrayList());

        HashSet visited = new HashSet();

        // Call dfs starting from "A" and print visited
        // Your code here
    }

    public static void dfs(HashMap> graph, String city, HashSet visited) {
        if (visited.contains(city)) {
            return;
        }
        visited.add(city);
        for (String neighbor : graph.get(city)) {
            dfs(graph, neighbor, visited);
        }
    }
}

Hint

Call dfs(graph, "A", visited); and then print visited using System.out.println(visited);.

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