Solution Depth First Search

Problem Statement

Write Recursive Approach for Depth First Search (DFS).

Given a graph, perform Depth First Search (DFS) traversal on the graph using a recursive approach.

Example 1:

Graph:

    1 -- 2
   / \    \
  3   4 -- 5

Output: 1 2 5 4 3
Explanation: Starting from node 1, we visit its adjacent nodes in order: 2, 5, and 4. From node 4, we visit node 3.

Example 2:

Graph:

   0 -- 1 -- 3
    \  |
      2

Output: 0 1 3 2
Explanation: Starting from node 0, we visit its adjacent nodes in order: 1 and 2. From node 1, we visit node 3.

Example 3:

Graph:

   0 -- 1
   |    |
   3 -- 2

Output: 0 1 2 3
Explanation: Starting from node 0, we visit its adjacent nodes in order: 1 and 3. From node 1, we visit node 2.

Solution

The recursive DFS approach involves visiting each node of the graph and recursively visiting its adjacent nodes. The algorithm can be implemented as follows:

Create a recursive function, dfs, that takes a node and a visited set as parameters.
If the current node is not in the visited set, add it to the visited set and print its value.
Recursively call dfs on each unvisited adjacent node of the current node.

The base case for the recursive function is when the current node is already visited.

Codes

Here is the code for this algorithm:

java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {

  private int V; // Number of vertices
  private List<List<Integer>> adj; // Adjacency list

  private void initializeGraph(int V) {
    this.V = V;
    adj = new ArrayList<>(V);
    for (int i = 0; i < V; i++) {
      adj.add(new ArrayList<>());
    }
  }

  private void addEdge(int u, int v) {
    adj.get(u).add(v);
    adj.get(v).add(u);
  }

  private void DFSExe(
    int startNode,
    Set<Integer> visited,
    List<Integer> depthFirstSearch
  ) {
    visited.add(startNode);
    depthFirstSearch.add(startNode);

    for (int neighbor : adj.get(startNode)) {
      if (!visited.contains(neighbor)) {
        DFSExe(neighbor, visited, depthFirstSearch);
      }
    }
  }

  public List<Integer> DFS(List<List<Integer>> args, int n, int first) {
    initializeGraph(n);
    List<Integer> depthFirstSearch = new ArrayList<>();

    for (int i = 0; i < args.size(); i++) {
      List<Integer> num = args.get(i);
      addEdge(num.get(0), num.get(1));
    }

    DFSExe(first, new HashSet<>(), depthFirstSearch);
    return depthFirstSearch;
  }

  public static void main(String[] args) {
    // Example graph represented as a 2D List
    List<List<Integer>> graphEdges = new ArrayList<>();
    graphEdges.add(List.of(1, 2));
    graphEdges.add(List.of(1, 5));
    graphEdges.add(List.of(2, 4));
    graphEdges.add(List.of(4, 5));
    graphEdges.add(List.of(3, 5));

    Solution graph = new Solution();

    System.out.print("DFS traversal: ");
    List<Integer> result = graph.DFS(graphEdges, 6, 1);

    // Print the DFS result
    for (int vertex : result) {
      System.out.print(vertex + " ");
    }
  }
}

Time and Space Complexity

The time complexity of the DFS algorithm using recursion is , where V is the number of vertices and E is the number of edges in the graph. This is because, in the worst case, we visit all the vertices and edges of the graph. The space complexity is , where V is the number of vertices, due to the space used for the visited set.

🤖 Don't fully get this? Learn it with Claude

Stuck on Solution Depth First Search? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Solution Depth First Search** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Solution Depth First Search** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Solution Depth First Search**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Solution Depth First Search**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Solution Quick Sort Solution Removing Nodes From Linke →